f*******r
发帖数: 1086 | 1 今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
题目：
A sequence of numbers is called a zig-zag sequence if the differences betwee
n successive numbers strictly alternate between positive and negative. The f
irst difference (if one exists) may be either positive or negative. A sequen
ce 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 n |
x******3
发帖数: 245 | 2 没看懂你的解法，
比如这段程序，
if(DiffArray[i]*DiffArray[i+1] < 0)
你只是判断相邻的三个元素是不是zig zag，
但是longest zz subsequence里的元素不一定要相邻
能说下你的subproblem space是什么吗
我的subproblem定义是
给定序列A[1..n]
LCCZ(i) = the length of longest ZZ subsequence ending at A[i]
原题的解LCCZ(A) = max(A[i]) 1<=i<=n |
B*****t
发帖数: 335 | 3 想复杂了，这个贪心就可以了, 设置个flag， s[i]>s[i-1]， flag=true,
s[i]
flag=true的时候，如果s[i]>=s[i-1],i++ 直到s[i]
反之类似。
differences betwee
negative. The f
negative. A sequen
sequence.
differences (6,-3
1,4,7,2,5 and 1
first two differen
zero.
【在 f*******r 的大作中提到】
: 今天看了一道DP题目，自己写了一个函数，请大家看看是否有问题:
: 题目：
: A sequence of numbers is called a zig-zag sequence if the differences betwee
: n successive numbers strictly alternate between positive and negative. The f
: irst difference (if one exists) may be either positive or negative. A sequen
: ce 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 n
|
x******3
发帖数: 245 | 4 不是很理解，能run个例子吗
【在 B*****t 的大作中提到】
: 想复杂了，这个贪心就可以了, 设置个flag， s[i]>s[i-1]， flag=true,
: s[i]: flag=true的时候，如果s[i]>=s[i-1],i++ 直到s[i]: 反之类似。
:
: differences betwee
: negative. The f
: negative. A sequen
: sequence.
: differences (6,-3
|
h**6
发帖数: 4160 | 5 这是Topcoder上的题吧。
遍历一遍就可以了：
如果当前和前一个相等，则跳过
如果当前应该比前一个大实际也比前一个大，计数加1，标志翻转
如果当前应该比前一个小实际也比前一个小，计数加1，标志翻转
每次循环必须更新当前数和前一个数，仅计数加1的时候标志才翻转。 |
B*****t
发帖数: 335 | 6 如 1 3 2 1 4
3>1 flag=true; res = 2;
2<3 flag=!flag; res++;
1<2 continue;
4>1 flag=!flag; res++;
每次flag翻转的时候res++；
【在 x******3 的大作中提到】
: 不是很理解，能run个例子吗
|
x******3
发帖数: 245 | 7 对于第一个数怎么处理
自动计入longest ZZ subsequence吗
【在 h**6 的大作中提到】
: 这是Topcoder上的题吧。
: 遍历一遍就可以了：
: 如果当前和前一个相等，则跳过
: 如果当前应该比前一个大实际也比前一个大，计数加1，标志翻转
: 如果当前应该比前一个小实际也比前一个小，计数加1，标志翻转
: 每次循环必须更新当前数和前一个数，仅计数加1的时候标志才翻转。
|
d****n
发帖数: 233 | 8 int longestZigZag(int sequence[], int num)
{
// arguments validation skipped
int s= 1;
while (s < num && sequence[s] == sequence[s-1])
s++;
if (s == num ) return 1;
int count = 2;
int increasing = (sequence[s]-sequence[s-1] > 0)?1:-1;
while (s < num)
{
if (increasing*(sequence[s]-sequence[s-1]) < 0)
{
++count;
increasing *= -1;
}
++s;
}
return count;
}
【在 x******3 的大作中提到】
: 对于第一个数怎么处理
: 自动计入longest ZZ subsequence吗
|
x******3
发帖数: 245 | 9 多谢BlueAnt和durbin， 终于是想明白了 |
f*******r
发帖数: 1086 | 10 谢谢指点，呵呵，大家说的对，
我想错了，总以为longest subsequence要是continuous的序列，
应该是这样简单比较就可以了，还不需要
额外分配空间，谢谢！
【在 B*****t 的大作中提到】
: 想复杂了，这个贪心就可以了, 设置个flag， s[i]>s[i-1]， flag=true,
: s[i]: flag=true的时候，如果s[i]>=s[i-1],i++ 直到s[i]: 反之类似。
:
: differences betwee
: negative. The f
: negative. A sequen
: sequence.
: differences (6,-3
|
|
|
b****j
发帖数: 78 | |
K******g
发帖数: 1870 | |
l*****a
发帖数: 14598 | 13 大家都想明白了？
这个结果我觉得不正确把。
你的算法是如果当前的状态跟上次的状态不一致，则++
如果一样，则不计数。
这样的话，请看 1，4，3，10，9，8，6 ，7，6，9
差值为 3，-1，7，-1，-1，-1，1，-1，3
当扫描到10/9的时候，与3/10不同还可以++，然后9/8，8/6都是递减，跳过
然后6/7是增加了，按照大家的算法，长度可以++了
可实际上这样的序列就是 1，4，3，10，9，（6）7
其实最后还是两次数值下降，这样的结果应该是不正确的吧
难道我什么地方理解得有问题？
欢迎指正
【在 f*******r 的大作中提到】
: 谢谢指点，呵呵，大家说的对，
: 我想错了，总以为longest subsequence要是continuous的序列，
: 应该是这样简单比较就可以了，还不需要
: 额外分配空间，谢谢！
|
y*****i
发帖数: 727 | |
d****k
发帖数: 41 | 15 这个算法貌似还有些问题，比如
输入：［3，3，3］
期盼输出：0
实际输出：1
【在 d****n 的大作中提到】
: int longestZigZag(int sequence[], int num)
: {
: // arguments validation skipped
: int s= 1;
: while (s < num && sequence[s] == sequence[s-1])
: s++;
: if (s == num ) return 1;
: int count = 2;
: int increasing = (sequence[s]-sequence[s-1] > 0)?1:-1;
: while (s < num)
|
d****k
发帖数: 41 | 16 我也试试，请指教，C语言风格：
int longestZigZagSequence(int[] s, int size){
if(NULL == s || size < 0){
fprintf(stderr, "Incorrect parameters in longestZigZagSequence(...)!
")
exit(1);
} else if(size < 2) {
return 0;
}
int i;
int flag = 0;
int zzCount = 0;
for(i=1; i
if(s[i] == s[i-1]){
continue;
} else if(s[i] > s[i-1] && flag <= 0){
zzCount++;
flag = 1;
} else if(s[i] < s
【在 d****n 的大作中提到】
: int longestZigZag(int sequence[], int num)
: {
: // arguments validation skipped
: int s= 1;
: while (s < num && sequence[s] == sequence[s-1])
: s++;
: if (s == num ) return 1;
: int count = 2;
: int increasing = (sequence[s]-sequence[s-1] > 0)?1:-1;
: while (s < num)
|
l*****a
发帖数: 14598 | 17 please use some samples for testing
longestZigZagSequence(...)!
【在 d****k 的大作中提到】
: 我也试试，请指教，C语言风格：
: int longestZigZagSequence(int[] s, int size){
: if(NULL == s || size < 0){
: fprintf(stderr, "Incorrect parameters in longestZigZagSequence(...)!
: ")
: exit(1);
: } else if(size < 2) {
: return 0;
: }
: int i;
|
y*****i
发帖数: 727 | 18 测试下
1 2 1 2 1000 999 1000 999 1000 999 1000
)!
【在 d****k 的大作中提到】
: 我也试试，请指教，C语言风格：
: int longestZigZagSequence(int[] s, int size){
: if(NULL == s || size < 0){
: fprintf(stderr, "Incorrect parameters in longestZigZagSequence(...)!
: ")
: exit(1);
: } else if(size < 2) {
: return 0;
: }
: int i;
|
d****k
发帖数: 41 | 19 删除索引为3的元素，剩下的是一个最长的序列
..
【在 y*****i 的大作中提到】
: 测试下
: 1 2 1 2 1000 999 1000 999 1000 999 1000
:
: )!
|
x****r
发帖数: 99 | 20 不是很懂你的问题，但我觉得他们的意思是
10->9 ++
9->8 keep
8->6 keep
6->7 ++(这一步没有错，因为你只要放弃之前的9，选这个6，就可以满足zigzag条件）
7->6 ++
6->9 ++
所以我看好像是没错呀
【在 l*****a 的大作中提到】
: 大家都想明白了？
: 这个结果我觉得不正确把。
: 你的算法是如果当前的状态跟上次的状态不一致，则++
: 如果一样，则不计数。
: 这样的话，请看 1，4，3，10，9，8，6 ，7，6，9
: 差值为 3，-1，7，-1，-1，-1，1，-1，3
: 当扫描到10/9的时候，与3/10不同还可以++，然后9/8，8/6都是递减，跳过
: 然后6/7是增加了，按照大家的算法，长度可以++了
: 可实际上这样的序列就是 1，4，3，10，9，（6）7
: 其实最后还是两次数值下降，这样的结果应该是不正确的吧
|
y*****i
发帖数: 727 | 21 我理解错了，多谢指正！
【在 d****k 的大作中提到】
: 删除索引为3的元素，剩下的是一个最长的序列
:
: ..
|
K******g
发帖数: 1870 | 22 请问你怎么知道放弃前面的9呢，如果按照前面的代码，是不会放弃9的，除非我们加判
断条件。
【在 x****r 的大作中提到】
: 不是很懂你的问题，但我觉得他们的意思是
: 10->9 ++
: 9->8 keep
: 8->6 keep
: 6->7 ++(这一步没有错，因为你只要放弃之前的9，选这个6，就可以满足zigzag条件）
: 7->6 ++
: 6->9 ++
: 所以我看好像是没错呀
|
