Simple Java solution with a less-than-rigorous math proof


  • 0
    A
    public class Solution {
        public int wiggleMaxLength(int[] nums) {
            // algorithm 2017/06/04: it is easy to prove that we simply capture each point of inflection and we will get the longest wiggle subsequence
        /* proof: assume number1 is larger than number0, then we can test what if number2 is
            (1) larger than number1;
            (2) equal to number1;
            (3) less than number1 but larger than number0
            (4) equal to number0
            (5) less than number0
           in each case, skipping number1, by making number0=>number2, won't get a longer subsequence
        */
    
            if (null == nums || 0 == nums.length) {
                return 0;
            }
            if (1 == nums.length) {
                return 1;
            }
    
            // identify the first trend
            int index = 1;
            int diff  = -1;     // 1: upwards, 0: downwards
            for (; index < nums.length; index++) {
                if (nums[index] != nums[0]) {
                    diff = nums[index] > nums[0] ? 1 : 0;
                    break;
                }
            }
            if (-1 == diff) {
                // all numbers are equal
                return 1;   // a number itself is a wiggle sequence
            }
    
            // now find the remaining inflection points from index
            int countTrends = 1;
            for (; index < nums.length; index++) {
                if (nums[index] == nums[index-1]) continue;   // skip duplicated numbers
                if (1 == diff && nums[index] > nums[index-1]) continue;     // same upward trend
                if (0 == diff && nums[index] < nums[index-1]) continue;     // same downward trend
                // now trend changed, and we have an inflection
                countTrends++;
                diff = 1 - diff;
            }
            return 1 + countTrends;    // +1 for the first number
        }
    }

Log in to reply
 

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