Easy to understand Java O(n) DP solution


  • 0
    R

    Basic idea is using two array to store the wiggle length at each element as peak or valley, derive the current length from previous length.

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

Log in to reply
 

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