动态规划：寻找最长的锯齿子序列

Question

请问有人能够帮我理解一个问题的解决方案背后的核心逻辑吗？问题描述见这里。

所谓Zig Zag序列是指交替上升和下降的序列，例如1 3 2就是Zig Zag序列，但1 2 3则不是。任何仅包含一个或两个元素的序列都是Zig Zag序列。我们需要在给定序列中找到最长的Zig Zag子序列。与最长递增子序列问题不同，子序列中的元素不必连续，例如1 3 5 4 2可以有1 5 4作为其Zig Zag子序列。我们对最长的子序列感兴趣。

我明白这是一个动态规划问题，并且它非常类似于如何使用动态规划确定最长递增子序列。

我认为任何解决方案都需要一个外部循环来迭代不同长度的序列，而内部循环将必须遍历所有序列。

我们将在另一个数组dpStore中存储以索引i结尾的最长Zig Zag序列，因此中间结果被存储下来，并且稍后可以重复使用。这部分对于所有动态规划问题都是相同的。然后我们找到全局最大值并返回它。

我自己的解决方案显然是错误的，在这里粘贴只是想知道我的错误在哪里。

    private int isZigzag(int[] arr)
{
    int max=0;
    int maxLength=-100;
    int[] dpStore = new int[arr.length];

    dpStore[0]=1;

    if(arr.length==1)
    {
        return 1;
    }
    else if(arr.length==2)
    {
        return 2;
    }
    else 
    {           
        for(int i=3; i<arr.length;i++)
        {
            maxLength=-100;
            for(int j=1;j<i && j+1<=arr.length; j++)
            {
                if(( arr[j]>arr[j-1] && arr[j]>arr[j+1])
                    ||(arr[j]<arr[j-1] && arr[j]<arr[j+1]))
                {
                    maxLength = Math.max(dpStore[j]+1, maxLength);
                }
            }
            dpStore[i]=maxLength;               
        }
    }
    max=-1000;
    for(int i=0;i<arr.length;i++)
    {
        max=Math.max(dpStore[i],max);
    }
    return max; 
}

- Abhijeet Kashnia

---

您的第一个链接需要注册才能访问。如果问题描述嵌入到您的问题中，回答将会更容易。 - hammar

抱歉我没有注意到那个问题...我会快速陈述一下。 - Abhijeet Kashnia

你是否了解如何解决基本的最长上升子序列（不包括之字形）？这只是对其进行轻微修改，使用相同的技术来解决。 - hugomg

在 1 3 5 4 2 中，整个序列是 zig-zag。您没有提及如何处理相等的数字，但是除了相等的数字，所有不是递增或递减的序列都不是 zig-zag 子序列（除了平凡的 1 或 2 元素序列）。那么，1 1 1 是递增还是递减？ - IVlad

好的，你提供的问题与你所描述的完全不同。请问你能决定需要哪一个方面的帮助吗？ - IVlad

Answer 1

这是您链接的问题内容：

一个数字序列被称为锯齿形序列，如果连续数字之间的差严格地在正数和负数之间交替变化。第一差（如果存在）可以是正数或负数。少于两个元素的序列是锯齿形序列。

例如，1,7,4,9,2,5是一个锯齿形序列，因为差值(6,-3,5,-7,3)交替为正数和负数。相比之下，1,4,7,2,5和1,7,4,5,5不是锯齿形序列，前者因为它的前两个差值是正数，后者因为它的最后一个差值是零。

给定一个整数序列sequence，返回sequence中最长的锯齿形子序列的长度。子序列通过从原始序列中删除一些元素（可能为零）而获得，保留其余元素的原始顺序。

这与您在帖子中描述的完全不同。以下是解决实际的topcoder问题的方法。

dp[i, 0] = maximum length subsequence ending at i such that the difference between the
           last two elements is positive
dp[i, 1] = same, but difference between the last two is negative

for i = 0 to n do     
   dp[i, 0] = dp[i, 1] = 1

   for j = 0 to to i - 1 do
    if a[i] - a[j] > 0
      dp[i, 0] = max(dp[j, 1] + 1, dp[i, 0])
    else if a[i] - a[j] < 0
      dp[i, 1] = max(dp[j, 0] + 1, dp[i, 1])
    

例子：

i        = 0  1   2  3   4   5   6   7  8   9
a        = 1  17  5  10  13  15  10  5  16  8 
dp[i, 0] = 1  2   2  4   4   4   4   2  6   6    
dp[i, 1] = 1  1   3  3   3   3   5   5  3   7
           ^  ^   ^  ^
           |  |   |  -- gives us the sequence {1, 17, 5, 10}
           |  |   -- dp[2, 1] = dp[1, 0] + 1 because 5 - 17 < 0.
           |  ---- dp[1, 0] = max(dp[0, 1] + 1, 1) = 2 because 17 - 1 > 0
     1 element
   nothing to do
 the subsequence giving 7 is 1, 17, 5, 10, 5, 16, 8, hope I didn't make any careless
 mistakes in computing the other values)

然后只需取两个“dp”数组的最大值即可。

- IVlad

---

这里的 dp 是什么？它是一个有2行n列的矩阵吗？ - SexyBeast

根据定义，对应于值13和15的dp [i] [1]应该是3而不是2。 - MrTambourineMan

嗨@IVlad，在计算出最大子数组的长度为7之后，你是如何获得实际的7个元素的？ - GP cyborg

这个问题也有一种线性解决方案，请参见下面的其他答案。 - n0rm1e

你能否为这个算法写一个递归关系式？ - Mohsin

Answer 2

这是一个更简单的解决方案

让原始数组A具有长度n。构建另一个仅包含0和1且长度为n-1的数组B。如果a[i]-a[i+1]>=0，则B[i]=0，否则B[i]=1。这可以在O(n)内完成。现在我们有了一个只包含0和1的数组，问题是要找到交替连续的0和1。 B中0的连续子数组将由其任一元素表示。例如： 如果B=[0,0,0,0,0, 1,0,0,0,1,0,1,1,1,0]，则我们可以将B减少为Br=[0,1,0,1,0,1,0]，这可以在O(n)内完成，实际上我们只需要找到Br的大小，这可以通过一次迭代完成。而这就是所给问题的答案。因此总复杂度是O(n)+O(n)=O(n)。 换句话说： 保留第一个元素。然后找到序列的单调增或单调减部分，并保留所有这些序列的最后一个元素。

更新：您需要在此过程中添加一个答案，因为您正在计算之字形的数量，而不是列表的长度。请注意栏杆帖问题：https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/

- surya

---

你能证明这个算法的最优性吗？ - Olayinka

Olayinka：如果算法必须读取长度为n的数组的每个元素，则无法比O(n)更好。 - hivert

@surya的解决方案对于 1 17 5 10 13 15 10 5 16 8 不起作用，这里 b 变成了 [1 0 1 1 1 0 0 1 0]，br 将变成 [1 0 1 0 1 0]，因此你的算法得到的结果是 6，但正确答案是 7。 - EmptyData

@EmptyData 如果我说错了，请纠正我，但我认为您需要将 br 的长度加1。毕竟，如果整个数组是之字形，br 将只有 n-1 个元素。想想 a = [1,2]，b=br=[1] 的情况。话虽如此，这个算法对我来说似乎是有效的。还有其他反例吗？ - danqing

已更新解决方案以澄清此问题。 - n0rm1e

我认为这是一个更加整洁的解决方案-https://cs.stackexchange.com/q/75063。我们不需要`Br`（额外的空格）。 - Angshuman Agarwal

Answer 3

还有一种贪心算法。

先选取第一个元素。然后找出包括第一个元素的连续序列中的最小或最大元素并选择它。

例如，如果序列是 1, 5, 7, 9, 2, 4，首先选择1，然后选择9，因为9是连续序列1, 5, 7, 9中的最大值。

以相同方式继续进行，并选择2和5。 使用相同的方法，计算示例的子序列：

1, 17, 5, 10, 13, 15, 10, 5, 16, 8

is: 1, 17, 5, 15, 5, 16, 8

- user434345

---

我们如何找到刚好比当前数大或小的下一个数？ - Shivendra

这种贪心算法能将复杂度降至O(n)吗？ - Shivendra

Answer 4

实际上，我认为得分最高的答案是正确的（IVlad's）。但我非常确定动态规划部分（外循环）不是必要的。

采用贪心算法，我们可以通过以下操作获得positive_end_seq[i]和negative_end_seq[i]：

    positive_end_seq[i] = negative_end_seq[i-1];
    negative_end_seq[i] = positive_end_seq[i-1];
    if (A[i-1] > A[i]) { // next element for positive_end_seq
       positive_end_seq[i] += 1; 
    }
    if (A[i-1] < A[i]) { // next element for negqtive_end_seq
       negative_end_seq[i] += 1;
    }
    // if (A[i-1] == A[i]) values don't change

positive_end_seq[0] = 1 和 negative_end_seq[0] = 1，对于所有的i，这两个数组都包含以i为结尾的最长子序列的长度。我们不必查看0..i-2元素，并且证明这一点将是不错的。

时间复杂度为O（n）

当然，现在可以用计数器替换pos/neg数组，以下是Java代码：

    public static int subZigZag(int[] arr) {
      int pos_count = 1;
      int neg_count = 1;
      for(int i = 1; i < arr.length; ++i) {
        if (arr[i-1] < arr[i]) {
          pos_count = neg_count + 1;
        }
        if (arr[i-1] > arr[i]) {
          neg_count = pos_count+1;
        }
      }
      return Math.max(pos_count, neg_count);
    } 

- The_Ham

Answer 5

或者您可以使用贪心算法。

public static int longestZigZag(int[] sequence) {
    if (sequence.length==1) return 1;
    if (sequence.length==2) return 2;
    int[] diff = new int[sequence.length-1];

    for (int i=1;i<sequence.length;i++){
        diff[i-1]=sequence[i]-sequence[i-1];
    }
    int prevsign=sign(diff[0]);
    int count=0;
    if (prevsign!=0)
        count=1;
    for (int i=1;i<diff.length;i++){
        int sign=sign(diff[i]);
        if (prevsign*sign==-1){
            prevsign=sign;
            count++;
        }
    }
    return count+1;
}

public static int sign(int a){
    if (a==0) return 0;
    return a/Math.abs(a);
}

- Aydar Omurbekov

Answer 6

int zigzag(int[] a) {

List<Integer> list= new ArrayList<>();
int max = 0;
if(a.length==0 || a.length==1) return 0;
if(a.length==2) return 1;
for(int i=1;i<a.length-1;i++){

    if((a[i-1]<a[i] && a[i+1]<a[i]) || (a[i-1]>a[i] && a[i+1]>a[i])){
        if(list.isEmpty()){
           list.add(a[i-1]); 
        }
        list.add(a[i]);

    }else{
        list.add(a[i+1]); 
        max = Math.max(max,list.size());
        list.clear();
    }

}
return max;

}

- jchopra

---

你想解释一下你的答案吗？ - CodeF0x

Answer 7

这是如何在O(n)时间复杂度内完成的

public static int longestZigZag(int[] sequence) {
    if (sequence == null) {
        return 0;
    }

    int len  = sequence.length;
    if (len <= 2) {
        return len;
    }
    int minima = sequence[0];
    int maxima = sequence[0];
    int maximalen = 1;
    int minimalen = 1;

    for (int i = 1; i < len; i++) {
        if (sequence[i] < maxima) {
            if (minimalen < maximalen + 1) {
                minimalen = maximalen + 1;
                minima = sequence[i];
            } else if (minimalen == maximalen + 1 && sequence[i] < minima) {
                minima = sequence[i];
            }
        }
        if (sequence[i] > minima) {
            if (maximalen < minimalen + 1) {
                maximalen = minimalen + 1;
                maxima = sequence[i];
            } else if (maximalen == minimalen + 1 && sequence[i] > maxima) {
                maxima = sequence[i];
            }
        }
    }

    return Math.max(maximalen, minimalen);
}

- Sandip

Answer 8

public static int longestZigZag(int[] sequence) {
    int max_seq = 0;

    if (sequence.length == 1) {
        return 1;
    }

    if (sequence.length == 1) {
        return 2;
    }

    int dp[] = new int[sequence.length];

    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i < sequence.length; i++) {
        for (int j = i - 1; j > 0; j--) {
            if (((sequence[i] > sequence[j] &&
                sequence[j] < sequence[j - 1]) || 
                (sequence[i] < sequence[j] &&
                sequence[j] > sequence[j - 1])) &&
                dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;

                if (dp[i] > max_seq) {
                    max_seq = dp[i];
                }
            } 
        }
    }

    return max_seq;
}

- vishpat

Answer 9

这是我对简单贪心实现的看法。

正如其他人先前提到的那样，你只需要看一下最后三个点的“Zigzag”即可。

def zigzag(xs):
    res = xs[:2]
    for x in xs[2:]:
        if cmp(res[-1], x) == cmp(res[-1], res[-2]):
            res.append(x)
        else:
            res[-1] = x
    return res

- Thomas Ahle

Answer 10

选择局部极大值和局部极小值，非常简单。

vector<int> longest_oscilating_subsequence(const vector<int> seq) {
    vector<int> result; // the resulting subsequence 

    for (int i = 0; i < seq.size(); ++i) {
        if (i > 0 && seq[i] == seq[i - 1]) continue;

        // is this point a local extreme 
        bool local_max = true, local_min = true;
        if (i > 0) {
            local_max = local_max && (seq[i] >= seq[i - 1]);
            local_min = local_min && (seq[i] <= seq[i - 1]);
        }
        if (i < seq.size() - 1) {
            local_max = local_max && (seq[i] >= seq[i + 1]);
            local_min = local_min && (seq[i] <= seq[i + 1]);
        }

        // potentially add it to the sequence 
        if (local_max || local_min) result.push_back(seq[i]);
    }

    return result; 
}

- Lukas Mach