Very Simple Java Solution with detail explanation


  • 0
    X

    @llkk Here I tried to prove greedy solution: check if it helps.

    Suppose the given input sequence is [a0, a1, a2, ... , ai, ... , an]

    Say our greedy solution will always pick a0 into our final answer (according to algorithm given). And what we treat it, as an up element or a down element, is determined by comparing it with a1.

    Let's assume a0 < a1, so we are treating a0 as a down element.

    Now consider there is an optimal solution (opt) sequence starting with ai (0 <= i <= n).

    If ai is considered as an up element by opt, then we must have a0 >= ai, otherwise by appending a0 we can have a better solution sequence. The same idea when ai is treated as down element by opt.

    Thus, we can always replace ai with a0 so that we have another solution which is still optimal. Denote the new optimal solution with opt'.

    In opt`, if a0 is treated as up element, because a1 is larger than a0 according to our assumption, by replacing aj , which is the second element in opt', with a1 in opt' we can have another optimal solution opt''. Because we are picking both a0 and a1 and opt'' is also picking them, this will cause induction.

    if a0 is treated as down element, which is the same as our solution, we can delete a0 from input and start running both our algorithm and opt' from a1 instead. This will also cause induction.

    Omit the details of proving induction...


  • 0
    R

    I ran your code for input [1,17,5,10,7,3,4,2,3] although it outputs the correct max length. it picks up the wrong elements. I used sysout in both conditions to check which elements were being written to num using result. For the above it outputs 5 10 7 4 2 3 on console. It is incorrect because of the last three elements. It would be great if you could clarify how your code picks up 7 instead of 5 in the above input to correctly output max length as 8. Because it you choose both 10 and 7 te max length comes down to 5.


  • 0

    the keshavk's solution said : it can store the series too.
    but, it does not .
    for example:
    input :2,1,4,5,6,3,3,4,8,4
    output: 2, 1, 4, 3, 4, 4

    the last two nums does not satisified


  • 0

    This is greedy, not dp.

        public int wiggleMaxLength(int[] nums) {
          int n = nums.length;
          if(n <= 1) return n;
          int i = 1;
          for(; i < n; i++){
            if(nums[i] != nums[i - 1]) break; 
          }  
          if(i == n) return 1;
          boolean isIncreasing = nums[i] > nums[i - 1];
          i++;
          int max = 2;  
          for(; i < n; i++){
            if(isIncreasing && nums[i] < nums[i - 1]) {
              max++;
              isIncreasing = false;  
            } else if(!isIncreasing && nums[i] > nums[i - 1]){
              max++;
              isIncreasing = true;
            } 
          }  
          return max;  
        }

  • 0
    C

    I used the feature 1 * -1 = -1 and -1 * -1 = 1, to decide whether the next difference should be positive or negative.
    e.g.:
    1 (-1) 2 (1) 1 (-1) 3 the first two 1 and 2, the sign = 1, so next one should be less then 2, ie. (x - 1) * sign = -1. coz the 3rd is 1, which fits the condition. So the length of the longest subsequence + 1.

        public int wiggleMaxLength(int[] nums) {
            
            if (null == nums || 0 == nums.length) return 0;
            
            // record previous sign : + / -
            int sign = 0;
            // record the length of longest subseq
            int sum = 1;
            
            for (int i = 1; i < nums.length; i ++) {
                if (nums[i] == nums[i - 1]) continue;
                if (sign == 0) {
                    sign = (nums[i] - nums[i - 1]) > 0 ? 1 : -1;
                    sum ++;
                }
                else {
                    if ((nums[i] - nums[i - 1]) * sign < 0){
                        sum ++;
                        sign *= -1;
                    }
                }
            }
            
            return sum;
        }
    

  • 0

    At the beginning I thought it is a question about DF that the sequence can be"+ - + - + -" or "- + - + - +" .But then I found the question can convert to a greedy question. When the sequence starts as this pattern like "+ - + - + -",that means the best pattern is this.


Log in to reply
 

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