Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/376.html

 376	Wiggle Subsequence

 A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative.
 The first difference (if one exists) may be either positive or negative.
 A sequence with fewer than two elements is trivially a wiggle sequence.

 For example,
 [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative.

 In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive
 and the second because its last difference is zero.

 Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence.
 A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence,
 leaving the remaining elements in their original order.

 Example 1:

 Input: [1,7,4,9,2,5]
 Output: 6
 Explanation: The entire sequence is a wiggle sequence.

 Example 2:

 Input: [1,17,5,10,13,15,10,5,16,8]
 Output: 7
 Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

 Example 3:

 Input: [1,2,3,4,5,6,7,8,9]
 Output: 2


 Follow up:
 Can you do it in O(n) time?

 @tag-dp

Algorithm

DP

We maintain two dp arrays p and q,

  • p[i] indicates the maximum length of the swing subsequence with a positive first difference when the position i is reached
  • q[i] indicates the maximum length of the wobble sub-sequence with a negative first difference when reaching the i position

We traverse the array from i=1, and then for each traversed number, traverse to this number from the beginning position, then compare nums[i] and nums[j], and update the corresponding positions respectively.

Greedy

Maintain two variables p and q, and then traverse the array

  • If the current number is greater than the previous number, then p=q+1
  • If the current number is smaller than the previous number, then q=p+1

Finally, compare the larger value of p and q with n, and choose the smaller one.

Code

Java

  • import java.util.Arrays;
    
    public class Wiggle_Subsequence {
    
        public static void main(String[] args) {
            Wiggle_Subsequence out = new Wiggle_Subsequence();
            Solution s = out.new Solution();
    
            System.out.println(s.wiggleMaxLength(new int[]{1,17,5,10,13,15,10,5,16,8}));
        }
    
        public class Solution_greedy {
            public int wiggleMaxLength(int[] nums) {
                if (nums.length < 2) {
                    return nums.length;
                }
    
                int up = 1, down = 1, n = nums.length;
                for (int i = 1; i < n; ++i) { // start from 2nd
                    if (nums[i] > nums[i - 1]) up = down + 1;
                    else if (nums[i] < nums[i - 1]) down = up + 1;
                }
                return Math.min(n, Math.max(up, down));
            }
        }
    
        public class Solution_better_oN {
            public int wiggleMaxLength(int[] nums) {
                if (nums.length < 2) {
                    return nums.length;
                }
    
                int n = nums.length;
                int[] up = new int[n];
                int[] down = new int[n];
                up[0] = down[0] = 1;
                for (int i = 1; i < n; i++) {
                    if (nums[i] > nums[i - 1]) {
                        up[i] = down[i - 1] + 1;
                        down[i] = down[i - 1];
                    } else if (nums[i] < nums[i - 1]) {
                        down[i] = up[i - 1] + 1;
                        up[i] = up[i - 1];
                    } else { // @note: test case, input: [0,0]
                        down[i] = down[i - 1];
                        up[i] = up[i - 1];
                    }
                }
                return Math.max(down[n - 1], up[n - 1]);
            }
        }
    
        public class Solution { // o(N^2)
    
            // @note: could start with either up or down, both valid
            public int wiggleMaxLength(int[] nums) {
    
                if (nums.length < 2) {
                    return nums.length;
                }
    
                // up[i] refers to the length of the longest wiggle subsequence obtained so far
                //      considering i^th element as the last element of the wiggle subsequence and ending with a rising wiggle.
                int[] up = new int[nums.length];
    
                int[] down = new int[nums.length];
    
                Arrays.fill(up, 1); // initialization, each position is at least 1 for that char
                Arrays.fill(down, 1); // @note: or don't do this step, in final return just `1+()`
    
                for (int i = 1; i < nums.length; i++) {
                    for(int j = 0; j < i; j++) {
                        if (nums[i] > nums[j]) {
                            up[i] = Math.max(up[i],down[j] + 1);
                        } else if (nums[i] < nums[j]) {
                            down[i] = Math.max(down[i],up[j] + 1);
                        }
                    }
                }
    
                return Math.max(down[nums.length - 1], up[nums.length - 1]);
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/wiggle-subsequence/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            int inc = 1, dec = 1, N = nums.size();
            for (int i = 1; i < N; ++i) {
                if (nums[i] > nums[i - 1]) inc = dec + 1;
                else if (nums[i] < nums[i - 1]) dec = inc + 1;
            }
            return max(inc, dec);
        }
    };
    
  • class Solution:
        def wiggleMaxLength(self, nums: List[int]) -> int:
            up = down = 1
            for i in range(1, len(nums)):
                if nums[i] > nums[i - 1]:
                    up = max(up, down + 1)
                elif nums[i] < nums[i - 1]:
                    down = max(down, up + 1)
            return max(up, down)
    
    ############
    
    class Solution(object):
      def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
          return 0
        up = down = 1
        for i in range(1, len(nums)):
          if nums[i] > nums[i - 1]:
            up = down + 1
          elif nums[i] < nums[i - 1]:
            down = up + 1
        return max(up, down)
    
    

All Problems

All Solutions