Easy understanding DP solution with O(n), Java version


  • 35
    T

    For every position in the array, there are only three possible statuses for it.

    • up position, it means nums[i] > nums[i-1]
    • down position, it means nums[i] < nums[i-1]
    • equals to position, nums[i] == nums[i-1]

    So we can use two arrays up[] and down[] to record the max wiggle sequence length so far at index i.
    If nums[i] > nums[i-1], that means it wiggles up. the element before it must be a down position. so up[i] = down[i-1] + 1; down[i] keeps the same with before.
    If nums[i] < nums[i-1], that means it wiggles down. the element before it must be a up position. so down[i] = up[i-1] + 1; up[i] keeps the same with before.
    If nums[i] == nums[i-1], that means it will not change anything becasue it didn't wiggle at all. so both down[i] and up[i] keep the same.

    In fact, we can reduce the space complexity to O(1), but current way is more easy to understanding.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            
            if( nums.length == 0 ) return 0;
            
            int[] up = new int[nums.length];
            int[] down = new int[nums.length];
            
            up[0] = 1;
            down[0] = 1;
            
            for(int i = 1 ; i < nums.length; i++){
                if( nums[i] > nums[i-1] ){
                    up[i] = down[i-1]+1;
                    down[i] = down[i-1];
                }else if( nums[i] < nums[i-1]){
                    down[i] = up[i-1]+1;
                    up[i] = up[i-1];
                }else{
                    down[i] = down[i-1];
                    up[i] = up[i-1];
                }
            }
            
            return Math.max(down[nums.length-1],up[nums.length-1]);
        }
    }
    

  • 1
    Y

    Good DP solution with O(n).

    Just explain what is happening here :
    For each i, we do not need to compare all the previous conditions and update the max, cuz for both up and down array, it keeps increasing(+0 or +1) with either copying from last element or plus 1 operation.

    And, if we reduce the space to O(1). It would be the exactly same as the most up-voted greedy solution.


  • 0
    N

    good answer!!


  • 0
    J
    This post is deleted!

  • 6

    Very nice and easy to understand! It's really hard to understand if jump to the final version at the very first. Now I can do it myself like this :) DP is magic!!!

        public int wiggleMaxLength(int[] nums) {
            if (nums.length == 0) return 0;
            int up = 1, down = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] < nums[i - 1]) down = up + 1;
                else if (nums[i] > nums[i - 1]) up = down + 1;
            }
            return Math.max(up, down);
        }
    

  • 1
    R

    why should up = down + 1 when nums[i] > nums[i-1] ? What do "up" and "down" mean? The result is right but I cannot see the logic behind it. Could you explain it? Thank you.


  • 0
    O

    The DP solution is based on the greedy strategy that we will always use the current element will doing left-right scanning.


  • 0
    Z

    @Rhodey The DP version use O(n) space to record states, but if we exam it carefully, we find i state only depends on i - 1 state, hence we can rewrite to use only two variables instead of array with size n to record state. The logic is the same as OP explained.


  • 0

    Here is my solution using Recursion + Memo, same idea as DP. But I find recursion is more intuitive than iteration.

    public class Solution {
        
        int[][] mem;
        
        private int helper(int[] nums, int i, boolean up) {
            if(i==nums.length-2) {
                if(up)
                    return nums[i+1]>nums[i] ? 2 : 1;
                else
                    return nums[i+1]<nums[i] ? 2 : 1;
            }
            if(mem[i][up?0:1]>0)
                return mem[i][up?0:1];
            if(up) {
                int max = helper(nums,i+1,true);
                if(nums[i+1]>nums[i])
                    max = Math.max(1+helper(nums,i+1,false), max);
                mem[i][0] = max;
                return max;
            } else {
                int max = helper(nums,i+1,false);
                if(nums[i+1]<nums[i])
                    max = Math.max(1+helper(nums,i+1,true), max);
                mem[i][1] = max;
                return max;
            }
        }
        
        public int wiggleMaxLength(int[] nums) {
            if(nums.length<=1)
                return nums.length;
            mem = new int[nums.length][2];
            return Math.max(helper(nums, 0, true), helper(nums, 0, false));
        }
    }

  • 0

    @cdai said in Easy understanding DP solution with O(n), Java version:

    public int wiggleMaxLength(int[] nums) {
    	if (nums.length == 0) return 0;
    	int up = 1, down = 1;
    	for (int i = 1; i < nums.length; i++) {
    		if (nums[i] < nums[i - 1]) down = up + 1;
    		else if (nums[i] > nums[i - 1]) up = down + 1;
    	}
    	return Math.max(up, down);
    }
    

    It feels much like the Greedy way but the code is much shorter. The trick here is to use two variables (up and down) to keep track the count the since we don't know whether the last element will go 'up' or 'down'.

    The code is clean and easy to understand. Thanks!


  • 0
    T

    I would say this is actually also a greedy solution. It doesn't really care about what happens before or next.


Log in to reply
 

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