Wiggle Subsequence


  • 0

    Click here to see the full article post


  • 0
    L

    It would be better if you can prove and elaborate more on approach #3. :)


  • 0
    A

    The complexity of approach #1 should be O(2^n). Not O(n!). Could you please give your proof of O(n!)?


  • 0
    A

    Time complexity analysis for approach 1:

    Since T(n) = 2[T(n - 1) + T(n - 2) + ... + T(1)], (1)
    then T(n - 1) = 2[T(n - 2) + T(n - 3) + ... + T(1)], (2)
    which is T(n - 2) + T(n - 3) + ... + T(1) = (1/2) * T(n - 1), (3)
    from (1) and (3), we can get
    T(n) = 2[T(n - 1) + (1/2) * T(n - 1)]
    = 3 * T(n - 1)
    = (3^2) * T(n - 2)
    .
    .
    .
    = 3 ^ (n - 1) * T(1).
    And because of T(1) = 1, we can get T(n) = (1/3) * 3^n, (4)
    then we can say the time complexity is O(3^n).

    And from (4), T(n) >= (1/3) (2^n) = O(2^n).

    In summary, we can say approach #1 is exponential time.


  • 2
    A

    Hi, LASkuma. I volunteer to give a proof of the correctness of approach #3. Sorry I didn't notice that I make it so long :)

    #3 Approach

    From the approach, we can see it considers the maximum of the last elements of up array
    and down array as the result.

    The prove the approach is correct, we need to prove that "the maximum of the last elements
    of up array and down array as the result".

    This is equivalent to prove "the last element of a sequence would also be the last element
    of one of its longest wiggle sequence". -------------- (1)

    Proof by mathematical induction:

    Basis:

    (1) is naturally valid for sequences of size 1.

    Inductive step:

    Assume (1) is valid for any sequences of size k, where k >= 1. -------------- (2)

    Then considering a sequence of size (k + 1). We label it as A, that is {nums[1], nums[2], ...,
    nums[k], nums[k + 1]}).

    A's subsequence, which consists of first k elements, also satisfy (1). We label it as B,
    that is {nums[1], nums[2], ..., nums[k]}.

    Assume C is one of B's longest wiggle subsequences. C has nums[k] as its last element.
    Then there are there cases to consider:

    Case 1: nums[k] is in up wiggle, there are two cases for nums[k]:
    Case 1.1: nums[k] <= nums[k + 1]
    nums[k + 1] would keep the up wiggle continue. Therefore, replacing nums[k]
    with nums[k + 1] in C would result in a longest wiggle subsequence for A.
    Case 1.2: nums[k] > nums[k + 1]
    nums[k + 1] would stop the up wiggle, and starts a down wiggle. Therefore,
    appending nums[k + 1] to C would result in a longest wiggle subsequence for A.

    Case 2: nums[k] is in down wiggle,
    Case 2.1: nums[k] >= nums[k + 1]
    nums[k + 1] would keep the down wiggle continue. Therefore, replacing nums[k]
    with nums[k + 1] in C would result in a longest wiggle subsequence for A.
    Case 2.2: nums[k] < nums[k + 1]
    nums[k + 1] would stop the down wiggle, and starts an up wiggle. Therefore,
    appending nums[k + 1] to C would result in a longest wiggle subsequence for A.

    Case 3: nums[k] is not in any wiggle.
    Case 3.1: nums[k] = nums[k + 1]
    nums[k + 1] would still make no wiggle. Therefore, replacing nums[k]
    with nums[k + 1] in C would result in a longest wiggle subsequence for A.
    Case 3.2: nums[k] < nums[k + 1]
    nums[k + 1] would start an up wiggle. Therefore, appending nums[k + 1] to C
    would result in a longest wiggle subsequence for A.
    Case 3.3: nums[k] > nums[k + 1]
    nums[k + 1] would start a down wiggle. Therefore, appending nums[k + 1] to C
    would result in a longest wiggle subsequence for A.

    From all these cases, we can say that nums[k + 1] is the last element of one of A's longest
    wiggle subsequence.

    Proved.


  • 0
    L

    @Aeonaxx Thank you very much!


  • 0

    We can do it a more short way

    int wiggleMaxLength(vector<int>& nums)
    {
        if (nums.size() < 2) return nums.size();
    
       int p = 0, len = 1;
    
       for (int i = 0; i < nums.size()-1; ++i)
       {
           if (nums[i] == nums[i+1]) continue;
    
           if ((nums[i]-nums[p])*(nums[i+1]-nums[i]) <= 0) p = i, ++len;
       }
    
       return len;
    

    }


  • 0

    I really don't understand: in your #1, do you assume the 1st element must be selected? Is there any case that the longest subsequence does not contains the 1st element?


  • 0
    S

    This might be mich easier than the methods given above:
    Logic - We just need to be going forward until a desirable difference is found, and then repeat with that difference.

    int mlength=n,diff=0;
        for(int i=1; i<n;i++){
            if(nums[i]==nums[i-1])
                mlength--;
            
            else if(nums[i]-nums[i-1]>0 && diff<=0 || nums[i]-nums[i-1]<0 && diff>=0)
                diff=nums[i]-nums[i-1];
                
            else
                mlength--;
        }
        
        return mlength;

  • 0
    U

    this is a easy cake.


  • 0
    S

    Approach #5 in Ruby follows.

    def longest_wiggle(arr)
      arr.each_cons(2).
          reject { |a,b| a==b }.
          map(&:first).
          push(arr.last).
          each_cons(3).
          select { |triple| [triple.min, triple.max].include? triple[1] }.
          map { |_,n,_| n }.
          unshift(arr.first).
          push(arr.last)
    end
    

    The first four lines (through push(arr.last).) are to convert each sequence of adjacent equal values to one instance of the value (e.g., [1,2,2,2,3,4,4,] => [1,2,3,4]). If the data contain no such sequences those lines can be removed and the next line changed to arr.each_cons(3)..


  • 0
    S

    Chidong, you asked, "Is there any case that the longest subsequence does not contains the 1st element?". Suppose the first two elements of a longest subsequence are at indices i > 0 and j > i. Suppose further that x(i) > x(j). If x(k) < x(i) for any k < i, a longer subsequence could be obtained by starting at x(k), a contradiction. That implies x(i-1) >= x(i), which contradicts the assumption that x(i) is a peak or valley bottom. A similar argument can be made when x(i) < x(j). It follows that all longest subsequences must begin with the first element of the array, and, by a similar argument, end with the last element of the array.


  • 0
    M

    @swoveland you probably should add another

    each_cons(2).reject{|a,b| a==b }.map(&:first).push(arr.last)
    

    at the end because you could end up with an array [x,x] where the first and last element of arr are the same (x) and you would not pass.


  • 0
    S

    @momolog, I don't understand how one could end up with [x,x]. If the array has no wiggles (e.g., all values equal x), an empty array would be returned. If the first and last values are x and at least one value is not x, there would be at least one wiggle, meaning that the array returned would have at least three elements. No? Could you give an example? Can you or someone else give me a link that explains how comments and answers are to be formatted on leetcode?


  • 0
    M

    @swoveland you can pass e.g. [2,2] or [2,2,2] to your method, which will both return [2,2], which is clearly not a wiggle sequence. It is because you are removing duplicate consecutive pairs in the first step - but in the last step unshift and push two elements that might be equal.

    As for formatting: it's standard markdown: either enclose your code block in a pair of ``` or indent all lines with 4 spaces.


  • 0
    S

    @momolog, thanks for pointing that out. How about adding this at the beginning of the method: return [] if arr.uniq.size == 1.


Log in to reply
 

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