leetcode 376. 摆动序列

解法1：贪心。
除去中间单调的节点即可。

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n=nums.length;
        int ans=1;
        int prevSub=0;
        for(int i=1;i=0)||(sub>0&&prevSub<=0)){
                ans++;
                prevSub=sub;
            }
        }
        return ans;
    }
}

解法2：动态规划。

dp[i][0]: 以nums[i]结尾且结尾是山峰的子序列长度
dp[i][1]: 以nums[i]结尾且结尾是山谷的子序列长度

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n=nums.length;
        int[][] dp=new int[n][2];
        dp[0][0]=1;
        dp[0][1]=1;
        for(int i=1;inums[j]){
                    dp[i][0]=Math.max(dp[i][0],dp[j][1]+1);
                }
            }
            for(int j=0;j