Wiggle Subsequence

题面

这题，自己写，一点思路都没有！后来看了题解，觉得作者分析得有道理！首先，这个所谓的摆动序列可以分为上升摆动序列，也可分为下降摆动序列。上升摆动序列是最后一个元素相对来说值偏大，使得整个序列呈上升趋势，那么下降摆动序列也就能理解了。上升摆动序列我们可以用up数组表示，up[i]就表示到数组中i这个位置以来的最长上升摆动序列，那么down[i]就表示到i这个位置以来的最长下降摆动序列。那么，我们就可以来动态规划了！我们通过动态规划算出这两个数组，最后取第n-1位的二者的最大值就行了。

首先显而易见，如果nums[i-1]nums[i]时，关系也就很自然能出来了。特别要注意的是，如果nums[i]=nums[i-1],这个时候既不是上升摆动序列也不是下降摆动序列，所以down[i]=down[i-1],up[i]=up[i-1].

 1 public int wiggleMaxLength(int[] nums) {
 2         int n = nums.length;
 3         if (n < 2) {
 4             return n;
 5         }
 6         int[] up = new int[n];
 7         int[] down = new int[n];
 8         up[0] = 1; down[0] = 1;
 9         for (int i = 1; i < n; ++i) {
10             if (nums[i-1] < nums[i]) {
11                 up[i] = down[i-1] + 1;
12                 down[i] = down[i-1];
13             } else if (nums[i-1] > nums[i]) {
14                 up[i] = up[i-1];
15                 down[i] = up[i-1] + 1;
16             } else {
17                 up[i] = up[i-1];
18                 down[i] = down[i-1];
19             }
20         }
21         return Math.max(up[n-1], down[n-1]);
22 }