动态规划：找到最长子是曲折 [英] Dynamic programming: Find longest subsequence that is zig zag
问题描述
任何人都可以请帮助我了解该解决方案以<一提到一个问题，背后的核心逻辑href="http://www.top$c$cr.com/stat?c=problem_statement&pm=1259&rd=4493">http://www.top$c$cr.com/stat?c=problem_statement&pm=1259&rd=4493
一个Z字形序列是交替地增大和减小。这样，1 3 2是锯齿形，但1 2 3不是。的一种或两种元素的任意序列是锯齿形。我们需要找到在给定的序列中的最长的锯齿形序列。亚序列意味着没有必要为元件是连续的，就像在最长递增子问题。因此，1 3 5 4 2可以有1 5 4作为一个曲折序列。我们感兴趣的是最长的一个。
据我所知，这是一个动态规划问题，这是非常相似的<一href="http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming">How使用动态规划来确定最长递增子？。
我认为，任何解决方案都需要一个外环，它迭代不同的长度，并且所述内环的序列将必须遍历所有序列
我们将存储时间最长的锯齿形序列索引i在另一个数组结尾，说dpStore索引i。所以，中间结果被存储，并可以稍后被重新使用。这部分是所有动态规划问题。后来我们发现全球最大和返回。
我的解决方案肯定是不对的，贴在这里展示一下我到目前为止。我想知道我在哪里出了问题。
私人诠释isZigzag（INT [] ARR）
{
INT最大= 0;
INT最大长度= -100;
INT [] dpStore =新INT [arr.length]
dpStore [0] = 1;
如果（arr.length == 1）
{
返回1;
}
否则，如果（arr.length == 2）
{
返回2;
}
其他
{
的for（int i = 3; I＆LT; arr.length;我++）
{
最大长度= -100;
为（诠释J = 1; J＆其中; I＆安培;＆安培; J + 1＆其中; = arr.length; J ++）
{
如果（（ARR [J] GT;常用3 [J-1]安培;＆放大器;常用3 [J] GT;常用3 [J + 1]）
||（ARR [J]其中，常用3 [J-1]安培;＆放大器;常用3 [J]其中，常用3 [J + 1]））
{
最大长度= Math.max（dpStore [J] +1，最大长度）;
}
}
dpStore [我] =最大长度;
}
}
最大= -1000;
的for（int i = 0; I＆LT; arr.length;我++）
{
最大= Math.max（dpStore [I]，最大值）;
}
返回最大值;
}
这就是你链接的问题说：
号的序列称为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字形序列的长度。通过删除从原始序列的元素（可能是零）的一些号码，留下它们原来的顺序，其余元素得到的序列。
这是从你在帖子中描述的完全不同。下面解决了实际的顶部codeR问题。
DP [我，0] =最大长度序列，在结束我这样的差别
最后两个元素是正
DP〔I，1] =相同，但最后两个之间差是负的
对于i = 0到n做
DP [I，0] = DP〔Ⅰ，1] = 1
对于j = 0至i - 1做
如果A [1] - 一个[J]≥ 0
DP [I，0] =最大值（DP [J，1] + 1，DP [I，0]）
否则，如果一个[I] - 一个[j]的＆其中; 0
DP〔I，1] =最大值（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 10 16 8
DP [I，0] = 1 2 2 4 4 4 4 2 6 6
DP〔I，1] = 1 1 3 3 2 2 5 5 3 7
^^^^
| | | - 为我们提供了序列{1，17，5，10}
| | - DP [2，1] = DP [1,0] + 1，因为5 - 17＆其中; 0。
| ---- DP [1,0] =最大值（DP [0，1] + 1，1）= 2，因为17 - 1＆GT; 0
1元
没事做
子序列给予7为1，17，5，10，5，16，8，希望我没有做任何马虎
在计算其它值的错误）
然后只取两个 DP 阵列的最大
Can anyone please help me understand the core logic behind the solution to a problem mentioned at http://www.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493
A zig zag sequence is one that alternately increases and decreases. So, 1 3 2 is zig zag, but 1 2 3 is not. Any sequence of one or two elements is zig zag. We need to find the longest zig zag subsequence in a given sequence. Subsequence means that it is not necessary for elements to be contiguous, like in the longest increasing subsequence problem. So, 1 3 5 4 2 could have 1 5 4 as a zig zag subsequence. We are interested in the longest one.
I understand that this is a dynamic programming problem and it is very similar to How to determine the longest increasing subsequence using dynamic programming?.
I think any solution will need an outer loop that iterates over sequences of different lengths, and the inner loop will have to iterate over all sequences.
We will store the longest zig zag sequence ending at index i in another array, say dpStore at index i. So, intermediate results are stored, and can later be reused. This part is common to all Dynamic programming problems. Later we find the global maximum and return it.
My solution is definitely wrong, pasting here to show what I've so far. I want to know where I went wrong.
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;
}
This is what the problem you linked to says:
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.
This is completely different from what you described in your post. The following solves the actual topcoder problem.
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])
Example:
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 2 2 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)
Then just take the max of both dp arrays.
这篇关于动态规划：找到最长子是曲折的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
