ZigZag - TopCoder

Longest Zig-Zag Subsequence - GeeksforGeeks
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

动态规划题。如果不用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数组下标从小到大，顺推。

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