ZigZag - TopCoder
Longest Zig-Zag Subsequence - GeeksforGeeks
The longest Zig-Zag subsequence problem is to find length of the longest subsequence of given sequence such that all elements of this are alternating.
If a sequence {x1, x2, .. xn} is alternating sequence then its element satisfy one of the following relation :
http://www.cnblogs.com/lautsie/p/3250929.html
http://rafal.io/posts/topcoder-zigzag.html
Z(i,0)Z(i,1)Z(0,0)Z(0,1)=minj<i,A[j]<A[i](Z(j,1)+1)=minj<i,A[j]>A[i](Z(j,0)+1)=1=1
Read full article from Longest Zig-Zag Subsequence - GeeksforGeeks
Longest Zig-Zag Subsequence - GeeksforGeeks
The longest Zig-Zag subsequence problem is to find length of the longest subsequence of given sequence such that all elements of this are alternating.
If a sequence {x1, x2, .. xn} is alternating sequence then its element satisfy one of the following relation :
x1 < x2 > x3 < x4 > x5 < …. xn or x2 > x2 < x3 > x4 < x5 > …. xn
Input: arr[] = {10, 22, 9, 33, 49, 50, 31, 60} Output: 6 The subsequences {10, 22, 9, 33, 31, 60} or {10, 22, 9, 49, 31, 60} or {10, 22, 9, 50, 31, 60} are longest Zig-Zag of length 6.
This problem is an extension of longest increasing subsequence problem, but requires more thinking for finding optimal substructure property in this.
We will solve this problem by dynamic Programming method, Let A is given array of length n of integers. We define a 2D array Z[n][2] such that Z[i][0] contains longest Zig-Zag subsequence ending at index i and last element is greater than its previous element and Z[i][1] contains longest Zig-Zag subsequence ending at index i and last element is smaller than its previous element, then we have following recurrence relation between them,
Z[i][0] = Length of the longest Zig-Zag subsequence ending at index i and last element is greater than its previous element Z[i][1] = Length of the longest Zig-Zag subsequence ending at index i and last element is smaller than its previous element Recursive Formulation: Z[i][0] = max (Z[i][0], Z[j][1] + 1); for all j < i and A[j] < A[i] Z[i][1] = max (Z[i][1], Z[j][0] + 1); for all j < i and A[j] > A[i]
The first recurrence relation is based on the fact that, If we are at position i and this element has to bigger than its previous element then for this sequence (upto i) to be bigger we will try to choose an element j ( < i) such that A[j] < A[i] i.e. A[j] can become A[i]’s previous element and Z[j][1] + 1 is bigger than Z[i][0] then we will update Z[i][0].
Remember we have chosen Z[j][1] + 1 not Z[j][0] + 1 to satisfy alternate property because in Z[j][0] last element is bigger than its previous one and A[i] is greater than A[j] which will break the alternating property if we update. So above fact derives first recurrence relation, similar argument can be made for second recurrence relation also.
Remember we have chosen Z[j][1] + 1 not Z[j][0] + 1 to satisfy alternate property because in Z[j][0] last element is bigger than its previous one and A[i] is greater than A[j] which will break the alternating property if we update. So above fact derives first recurrence relation, similar argument can be made for second recurrence relation also.
// Function to return longest Zig-Zag subsequence length
int
zzis(
int
arr[],
int
n)
{
/*Z[i][0] = Length of the longest Zig-Zag subsequence
ending at index i and last element is greater
than its previous element
Z[i][1] = Length of the longest Zig-Zag subsequence
ending at index i and last element is smaller
than its previous element */
int
Z[n][2];
/* Initialize all values from 1 */
for
(
int
i = 0; i < n; i++)
Z[i][0] = Z[i][1] = 1;
int
res = 1;
// Initialize result
/* Compute values in bottom up manner */
for
(
int
i = 1; i < n; i++)
{
// Consider all elements as previous of arr[i]
for
(
int
j = 0; j < i; j++)
{
// If arr[i] is greater, then check with Z[j][1]
if
(arr[j] < arr[i] && Z[i][0] < Z[j][1] + 1)
Z[i][0] = Z[j][1] + 1;
// If arr[i] is smaller, then check with Z[j][0]
if
( arr[j] > arr[i] && Z[i][1] < Z[j][0] + 1)
Z[i][1] = Z[j][0] + 1;
}
/* Pick maximum of both values at index i */
if
(res < max(Z[i][0], Z[i][1]))
res = max(Z[i][0], Z[i][1]);
}
return
res;
}
http://www.cnblogs.com/lautsie/p/3250929.html
动态规划题。如果不用DP,暴力的应当在2^n*n的复杂度吧。动态规划现在我的思维还老停留在一维而且没有第二层循环。但其实如果一开始的复杂度很高,稍微有几个循环,指数级别,一点问题没有。
题目描述:给出n个数:A[1], A[2], ... , A[n],求最长的子序列的长度,子序列中相邻数之间的差值是正负交替出现的。
f1[i]表示 最后一个数是A[i]并且A[i]和前一个数的差值为正的最长子序列的长度。
f2[i]表示最后一个数是A[i]并且A[i]和前一个数的差值为负的最长子序列的长度。
对于f1[i], 和它有联系的子问题是f2[j] (0<= j < i).f1[i] = max(f1[i], f2[j]+1) (A[i] > A[j])
对于f2[i], 和它有联系的子问题是 f1j] (0 <= j < I),f2[i] = max(f2[i], f1[j]+10 (A[i] < A[j])
计算子问题的顺序:A数组下标从小到大,顺推。
f1[i]表示 最后一个数是A[i]并且A[i]和前一个数的差值为正的最长子序列的长度。
f2[i]表示最后一个数是A[i]并且A[i]和前一个数的差值为负的最长子序列的长度。
对于f1[i], 和它有联系的子问题是f2[j] (0<= j < i).f1[i] = max(f1[i], f2[j]+1) (A[i] > A[j])
对于f2[i], 和它有联系的子问题是 f1j] (0 <= j < I),f2[i] = max(f2[i], f1[j]+10 (A[i] < A[j])
计算子问题的顺序:A数组下标从小到大,顺推。
public
int
longestZigZag(
int
[] sequence) {
if
(sequence.length ==
0
)
return
0
;
int
[] up =
new
int
[sequence.length];
int
[] down =
new
int
[sequence.length];
up[
0
] =
1
;
down[
0
] =
1
;
int
ret =
0
;
for
(
int
i =
1
; i < sequence.length; i++) {
int
max_up =
0
;
int
max_down =
0
;
for
(
int
j =
0
; j < i; j++) {
if
(sequence[j] > sequence[i]) {
if
(down[j] > max_down) max_down = down[j];
}
else
if
(sequence[j] < sequence[i]) {
if
(up[j] > max_up) max_up = up[j];
}
}
up[i] = max_down +
1
;
down[i] = max_up +
1
;
if
(up[i] > ret) ret = up[i];
if
(down[i] > ret) ret = down[i];
}
return
ret;
}
Let A an array of length of n of integers. Let Z(i,0) be the longest zig-zag subsequence ending at index i with a positive difference (the second last element of it is strictly less than the last element), and let Z(i,1) be the longest zig-zag subsequence ending at index i with a negative difference. Then:
public static int longestZigZag(int[] A){
int n = A.length;
int[][] Z = new int[n][2];
for(int i = 0; i < Z.length; i++){
Z[i] = new int[2];
}
Z[0][0] = 1;
Z[0][1] = 1;
int best = 1;
for(int i = 1; i < n; i++){
for(int j = i-1; j>= 0; j--){
if(A[j] < A[i]) Z[i][0] = Math.max(Z[j][1]+1,Z[i][0]);
if(A[j] > A[i]) Z[i][1] = Math.max(Z[j][0]+1, Z[i][1]);
}
best = Math.max(best, Math.max(Z[i][0],Z[i][1]));
}
return best;
}
https://github.com/detel/Algorithms/blob/master/DP/LongestZigZagSubsequence.javaRead full article from Longest Zig-Zag Subsequence - GeeksforGeeks