algorithm - 动态规划 : Find longest subsequence that is zig zag

Question

任何人都可以帮助我理解 http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493 中提到的问题的解决方案背后的核心逻辑吗？

之字形序列是交替增加和减少的序列。所以，1 3 2 是之字形，但 1 2 3 不是。一个或两个元素的任何序列都是之字形。我们需要找到给定序列中最长的之字形子序列。子序列意味着元素不必是连续的，就像在最长递增子序列问题中那样。因此，1 3 5 4 2 可能有 1 5 4 作为锯齿形子序列。我们对最长的感兴趣。

我知道这是一个动态规划问题，它与How to determine the longest increasing subsequence using dynamic programming? 非常相似。 .

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

我们将在另一个数组中存储以索引 i 结尾的最长之字形序列，例如索引 i 处的 dpStore。因此，中间结果会被存储起来，以后可以重复使用。这部分对于所有动态规划问题都是通用的。稍后我们找到全局最大值并将其返回。

我的解决方案肯定是错误的，粘贴在这里以展示我到目前为止的内容。我想知道我哪里出错了。

    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; 
}

Answer 1

这就是您链接到的问题所说的内容:

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

这与您在帖子中描述的完全不同。下面解决实际的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 数组的最大值。