Leetcode 376) Wiggle Subsequence

11 Aug 2021 in Algorithms

내 답안

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length==1){
            return 1;
        }
        int[] dif = new int[nums.length-1];
        for(int i =0;i<dif.length;i++){
            dif[i]=nums[i+1]-nums[i];
        }

        int cnt=2;
        if(dif[0]==0){
            cnt=1;
        }
        for(int i =1;i<dif.length;i++){
            while( dif[i]==0){
                dif[i]=dif[i-1];
                i++;
                if(i==dif.length){
                    return cnt;
                }
            }
            if(dif[i-1]==0){
                cnt++;
                continue;
            }
            if(dif[i-1]*dif[i]<0){
                cnt++;
            }           
        }

        return cnt;
    }
}

다른 답안

• 성능은 안 좋은데, dp로 푼 솔루션이다.

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