Java DP O(n^2) solution


  • 0
    W

    Define state dp[i]: ends with ith element, the maximum length wiggle subsequence. sign[i] means whether ith greater than previous one.
    Dp[i] = Max( dp[j] + 1 if (sign[j] > 0 and nums[i] < nums[j] or sign[j] < 0 and nums[i] > nums[j] or sign[j] == 0) for j from i - 1 to 0.

    public class Solution {

    public int wiggleMaxLength(int[] nums) {
        if (nums.length < 2) return nums.length;
     
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
    
        int[] sign = new int[nums.length]; 
        
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                /* handle duplicate element: it means that one won't contribute to the final result */
                if ((j > 0 && nums[j] == nums[j - 1]) || (nums[i] == nums[j])) {
                    continue;
                }
                if ((sign[j] > 0 && nums[i] < nums[j]) || (sign[j] < 0 && nums[i] > nums[j]) || sign[j] == 0) {
                    if (dp[i] < dp[j] + 1) {
                        if (nums[i] != nums[j]) {
                           sign[i] = nums[i] > nums[j] ? 1 : -1;
                        }
                        dp[i] = dp[j] + 1;
                    }
                }
            }
        }
        
        int v = Integer.MIN_VALUE;
        for (int a : dp) {
            v = Math.max(v, a);
        }
        
        return v;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.