3

method that needs to return the length of the longest subsequence of sequence that is a zig-zag sequence.The algorithmic approach should be dynamic programmingを書く必要があります。

連続する数の差が正と負の間で厳密に交互になる場合、数列はジグザグ数列と呼ばれます。最初の差異 (存在する場合) は、正または負のいずれかです。

Eg - 1,7,4,9,2,5   is a zig-zag sequence
because the differences (6,-3,5,-7,3) are alternately positive and negative. 

1,4,7,2,5 is not a zig-zag sequence.

私のコード:

public static int longestZigZag(int[] seq){

    int len = seq.length;
    int[] count= new int[len];

    for(int i=0;i<len;i++)
        count[i]=1;

    for(int i=1;i<len;i++){
        int k = (int)Math.pow(-1, i+1);

        if(seq[i]>(k*seq[i-1])){
            count[i]=count[i-1]+1;
        }
    }

    int max=1;
    for(int i=0;i<len;i++)
        if(count[i]>max)
            max=count[i];

    return max;
}

説明：

すべての要素に対応して、それまでcountの連続した交互シーケンスを表す要素があります。

seq:    1, 7, 4, 9, 2, 5
count:  1, 1, 1, 1, 1, 1

i=1 7 > 1    count[1]= count[0]+1 = 2
i=2 4 > -7   count[2]= count[1]+1 = 3
i=1 9 > 4    count[3]= count[2]+1 = 4
i=1 2 > -9   count[4]= count[3]+1 = 5
i=1 5 > 2    count[5]= count[4]+1 = 6

その後、カウント配列の最大値を出力するだけです。

エラー：

上記は正しく機能します

{ 1, 7, 4, 9, 2, 5 }                     ->  6
{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }   ->  7

ただし、それは間違った結果をもたらします

{ 1, 2, 3, 4, 5, 6, 7, 8, 9 } gives 9 but should be 2.
{ 70, 55, 13, 2, 99, 2, 80, 80, 80, 80, 100, 19, 7, 5, 
  5, 5, 1000, 32, 32 } gives 2 but should be 8.
4

1 に答える 1

1

これがどれほど答えられるかわかりません。. . あなたのアプローチは本当に完全に間違っています。:-/

これを確認するには、次のことを考慮してください。 の各要素の計算はcountの前の 1 つの要素のみに依存countし、 の実行中の計算maxは の現在の要素のみに依存しますcount。つまり、count配列さえ必要ないということです。アルゴリズム全体を、O(1) スペースを必要とする単一のパスに変換できます。しかし、「受験者」として、この問題はO(1) 空間を使用した 1 回のパスでは (簡単に) 解決できないことを知っています。 .

あなたのアルゴリズムが間違っている主な理由は、 の各要素seqをその直前の要素と比較するだけで、サブシーケンスは中間値を「飛び越える」ことが許可されている (そして通常はそうする) ことです。

出力のいくつかのより紛らわしい側面の原因となっている交絡要因の 1 つは、seq[i]>(k*seq[i-1])チェックが、あなたが意味すると私が考えていることを意味していないことです。あなたはおそらくもっと近いものを望んでいましk*(seq[i]-seq[i-1])>0たが、それでもかなり間違った結果が得られます. このアルゴリズムを破棄して、新しいアルゴリズムを作成する必要があります。

于 2012-11-16T16:39:13.190 に答える