Leetcode 376. Wiggle Subsequence

tags: Leetcode(JAVA)

題目 : https://leetcode.com/problems/wiggle-subsequence/ 。

想法 :

​​​​LIS改版。

時間複雜度 : O(n^2)。

程式碼 : (JAVA)

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int l=nums.length, ans=0;
        int[] dp=new int[l];
        int[] sign=new int[l];
        
        dp[0]=1;
        for(int i=1 ; i<l ; i++){
            if(nums[i] - nums[i-1] == 0) sign[i]=0;
            else if(nums[i] - nums[i-1] > 0) sign[i]=1;
            else{
                sign[i]=-1;
            }
            
            dp[i]=1;
        }
        
        for(int i=0 ; i<l ; i++){
            for(int j=0 ; j<=i ; j++){
                if(sign[i] * sign[j] < 0){
                    dp[i]=Math.max(dp[i], dp[j]+1);
                    ans=Math.max(ans, dp[i]);
                }
                else if(sign[i] * sign[j] > 0){
                    dp[i]=Math.max(dp[i], 1);
                    ans=Math.max(ans, dp[i]);
                }
                //System.out.printf("%d : %d %d %d %d\n", i, sign[i], sign[j], dp[i], dp[j]);
            }
        }
        
        return ans+1;
    }
}