摆动序列

1. 状态表示
   f[i] 表示以i位置为结尾, 最后呈"上升"趋势最长的摆动序列
   g[i] 表示以i位置为结尾, 最后呈"下降"趋势最长的摆动序列
2. 状态转移方程
   1.如果以i位置为开头 那么长度为1
   2.如果以i位置结尾, 由于不知道从前面哪一个位置取子序列, 所以要定义一个j(0 <= j <= i - 1), 找到以j位置结尾的所有子序列中, 最长的, 即dp[j]
   if(nums[j] < nums[i]){
   f[i] = Math.max(g[j] + 1, f[i]);
   }else if(nums[j] > nums[i]){
   g[i] = Math.max(f[j] + 1, g[i]);
   }
3. 初始化
   可以先全部初始化为1
4. 填表顺序
   从左往右
5. 返回值
   返回dp表中的最大值

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    f[i] = Math.max(g[j] + 1, f[i]);
                }else if(nums[j] > nums[i]){
                    g[i] = Math.max(f[j] + 1, g[i]);
                }
                ret = Math.max(ret, Math.max(f[i], g[i]));
            }
        }
        return ret;
    }
}