## Tuesday, December 1, 2015

### ZigZag - TopCoder

https://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493

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.

### Definition

 Class: ZigZag Method: longestZigZag Parameters: int[] Returns: int Method signature: int longestZigZag(int[] sequence) (be sure your method is public)

### Constraints

-sequence contains between 1 and 50 elements, inclusive.
-Each element of sequence is between 1 and 1000, inclusive.

### Examples

0)

 { 1, 7, 4, 9, 2, 5 }
Returns: 6
 The entire sequence is a zig-zag sequence.
1)

 { 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }
Returns: 7
 There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.
http://www.cnblogs.com/lautsie/p/3250929.html

f1[i]表示 最后一个数是A[i]并且A[i]和前一个数的差值为正的最长子序列的长度。
f2[i]表示最后一个数是A[i]并且A[i]和前一个数的差值为负的最长子序列的长度。

    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;
    }
http://rafal.io/posts/topcoder-zigzag.html
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:

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
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;
}