Java O(n) Solution with explaination - Easy to understand


  • 1
    M

    Notice that array dp[] will not decrease.

    curDiff records num[i]-nums[i-1]. preDiff mean the previous difference.
    The naive thought is that if curDiff >0 && preDiff<0 or curDiff <0 && preDiff>0, length should increase 1.
    But we need to be careful when num[i-1]-nums[i-2] == 0. If num[i-1]-nums[i-2] is 0, preDiff should record the previous difference that is not equal to 0. Or it will not contain any information. Then we can know next difference should be negative or positive.

        public int wiggleMaxLength(int[] nums) {
            if(nums==null || nums.length==0) return 0;
            final int N = nums.length;
            int[] dp = new int[N];
            dp[0] = 1;
            long curDiff=0, preDiff=0;
            for(int i=1; i<N; i++){
                if(curDiff != 0) preDiff = curDiff;
                curDiff = (long)nums[i]-nums[i-1];
                if((curDiff>0 && preDiff<=0) || (curDiff<0 && preDiff>=0)) {
                	dp[i] = dp[i-1]+1;
                } else 
                	dp[i] = dp[i-1];
            }
            return dp[N-1];
        }
        
    

  • 0
    F

    I don't think that solution is right, at least it is not the optimum solution.
    You can try [25,24,20,18,20,18,20,18]
    If you choose 25 as the first subsequence number, your answer must be 2. But if you choose 20 as the first number , your answer must be 6.

    You can get a subsequence matching condition by the way, but you can't get the max length.


  • 0
    M

    I just tried the case [25,24,20,18,20,18,20,18], and it output 6, actually.

    For [25,24,20,18,20,18,20,18], the array dp[] and the record of diff is like that :

    nums: [25, 24, 20, 18, 20, 18, 20, 18]
    dp:   [ 1,  2,  2,  2,  3,  4,  5,  6]
    diff: [ 0,  +,  +,  +,  -,  +,  -,  +]
    

  • 0
    M

    I don't know why I made the curDiff and preDiff be a long type at that time. Int is okay, even boolean.


Log in to reply
 

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