java - 使用动态规划的最长之字形子序列

Question

我需要编写一个方法，需要返回zig-zag序列的最长子序列的长度。算法方法应该是动态规划 .

---

一个数字序列称为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.

Answer 1

我不确定这有多负责任。 . .你的做法真的是完全错误的。 :-/

要了解这一点，请考虑以下几点:您对 count 的每个元素的计算仅取决于 count 的单个前一个元素，以及您对 的运行计算max 仅取决于 count 的当前元素。这意味着您甚至不需要 count 数组:您的整个算法可以转换为需要 O(1) 空间的单次传递。但是，作为“应试者”，您知道这个问题不能(轻松)在 O(1) 空间的单次通过中解决，因为如果它可以，你不会被指示使用动态规划。

你的算法错误的核心原因是你只将 seq 的每个元素与其直接前身进行比较，但允许子序列(并且通常会)“跳过”中间值。

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