Simple O(N) Time O(1) Space Java Solution with Explanation


  • 0
    K

    Positive represents the longest subsequence ending with positive wiggle. Negative represents the longest subsequence ending with negative wiggle. It's not possible that positive > negative + 1 or negative > positive + 1, otherwise positive or negative is not the longest subsequence. Thus we just need to update these two variables by scanning the array once.

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

Log in to reply
 

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