动态编程:找到最长的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作为之字形子序列.我们对最长的一个感兴趣.

我知道这是一个动态编程问题,它与如何使用动态编程确定增长最快的子序列非常相似？.

我认为任何解决方案都需要一个外循环来迭代不同长度的序列,内循环必须迭代所有序列.

我们将在索引i处存储最长的zig zag序列存储在另一个数组中,比如在索引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

这就是你所链接的问题:

如果连续数字之间的差异在正数和负数之间严格交替,则数字序列称为Z字形序列.第一个差异(如果存在)可以是正面的也可以是负面的.具有少于两个元素的序列通常是Z字形序列.

例如,1,7,4,9,2,5是Z字形序列,因为差异(6,-3,5,-7,3)交替为正和负.相比之下,1,4,7,2,5和1,7,4,5,5不是Z字形序列,第一个是因为它的前两个差异是正的,第二个是因为它的最后差异是零.

给定一系列整数序列,返回序列的最长子序列的长度,该序列是Z字形序列.通过从原始序列中删除一些元素(可能为零)来获得子序列,剩余的元素保持其原始顺序.

这与您在帖子中描述的完全不同.以下解决了实际的编码器问题.

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数组的最大值.

Answer 2

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

让原始数组A的长度为n.构建另一个长度为n-1且仅为0和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,0,0,0,0,1,0,1,1,1,0]那么我们可以将B减少到Br = [0,在O(n)中的1,0,1,0,1,0],实际上我们只需要找到Br的大小,这可以通过一次迭代来完成.我的朋友就是给定问题的答案.因此总复杂度为O(n)+ O(n)= O(n).换句话说:保留第一个元素.然后找到序列的单调生长或收缩部分,并保留所有这些序列中的最后一个元素.

更新:您需要在此过程中添加一个答案,因为您计算的是曲折,而不是列表的长度.谨防围栏问题:https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/

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

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