动态编程：查找最长的子序列之字形

一尘不染

动态编程：查找最长的子序列之字形

algorithm

任何人都可以帮助我了解 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结尾的最长的之字形序列存储在另一个数组中，例如在索引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; 
}

阅读 247

2020-07-28

共1个答案

一尘不染

这是您链接到的问题所说的：

如果连续数字之间的差严格在正负之间交替，则数字序列称为之字形序列。第一个差异（如果存在）可能为正或为负。少于两个元素的序列通常是Z字形序列。

例如，1,7,4,9,2,5是之字形序列，因为差异（6，-3,5，-7,3）交替为正和负。相反，1,4,7,2,5和1,7,4,5,5不是之字形序列，第一个不是它的前两个差为正，第二个是因为最后一个差为零。

给定一个整数序列，即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数组的最大值。

2020-07-28