3

我需要写一个method that needs to return the length of the longest subsequence of sequence that is a zig-zag sequence.算法方法应该是动态编程。

如果连续数字之间的差异在正负之间严格交替，则数字序列称为之字形序列。第一个差异（如果存在）可以是正面的也可以是负面的。

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仅取决于 的单个前一个元素count，而您对 的运行计算max仅取决于 的当前元素count。这意味着您甚至不需要count数组：您的整个算法可以转换为需要 O(1) 空间的单遍。但是，作为“应试者”，您知道这个问题不能（容易）在 O(1) 空间中一次性解决，因为如果可以，您就不会被指示使用动态规划.

您的算法错误的核心原因是您只会将 的每个元素seq与其直接前任进行比较，但允许（并且通常会）“跳过”中间值。

一个混淆因素是导致您的输出中一些更令人困惑的方面，即seq[i]>(k*seq[i-1])检查并不意味着我认为您认为它意味着什么。你可能想要更接近的东西k*(seq[i]-seq[i-1])>0——但即使这样也会给出非常错误的结果。你真的只需要废弃这个算法并编写一个新算法。

于 2012-11-16T16:39:13.190 回答