concise code with O(N) time complexity


  • -1
    S

    A general DP solution can solve it in O(N^2), but we can utilize more from the property of wiggle sequence-- we decide the next element need to be larger or smaller by the "length" of current longest sequence. At the same time, if we can extend current wiggle sequence, we update the last element, to make it more larger or more smaller than it orginal value.

    Besides, we can just do this two times, one is for " large, small, large, small.." another is for "small, larger, small, large.." and return the max.

    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums == null || nums.length == 0){
                return 0;
            }
            return Math.max(solve(nums, true), solve(nums, false));
        }
        int solve(int[] nums, boolean flag){
            int len = nums.length;
            int[] dp = new int[len];
            dp[0] = nums[0];
            int cur = 1;
            for (int i = 1; i < len; i++){
                if (nums[i] == dp[cur - 1]){
                    continue;
                }
                else if (cur % 2 != 0){
                    if ((nums[i] < dp[cur - 1]) != flag){
                        dp[cur++] = nums[i];
                    }
                    else {
                        dp[cur - 1] = nums[i];
                    }
                }
                else {
                    if ((nums[i] > dp[cur - 1]) != flag){
                        dp[cur++] = nums[i];
                    }
                    else {
                        dp[cur - 1] = nums[i];
                    }
                }
            }
            return cur;
        }
    }
    

Log in to reply
 

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