376. Wiggle Subsequence

Given an integer array nums, return the length of the longest wiggle sequence.

A wiggle sequence is a sequence where 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.

A subsequence is obtained by deleting some elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

• new solution update 2022.02.18

  class Solution {
      int dp[1001][2];
      int solution(vector<int>& nums, int p, bool upper) {
          if(p == nums.size()) return 0;
          if(dp[p][upper] != -1) return dp[p][upper];
          dp[p][upper] = 1;
          for(int i = p + 1; i < nums.size(); i++) {
              if((upper and nums[i] > nums[p]) or (!upper and nums[i] < nums[p])) {
                  dp[p][upper] = max(dp[p][upper], solution(nums, i, !upper) + 1);
              }
          }
          
          return dp[p][upper];
      }
  public:
      int wiggleMaxLength(vector<int>& nums) {
          memset(dp,-1,sizeof(dp));
          
          return max(solution(nums,0,true), solution(nums,0,false));
      }
  };

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        if(nums.size() == 1)
            return 1;
        pair<int, int> lower{1,nums[0]}, upper{1,nums[0]};

        for(int i = 1; i < nums.size(); i++) {
            pair<int, int> l = lower, u = upper;
            if(lower.second > nums[i]) {
                u = upper.first < lower.first + 1 ?
                        make_pair(lower.first + 1, nums[i]) : upper.first == lower.first + 1 ? upper.second > nums[i] ? make_pair(lower.first + 1, nums[i]) : upper : upper;
            }
            if(upper.second < nums[i]) {
                l = lower.first < upper.first + 1 ?
                        make_pair(upper.first + 1, nums[i]) : lower.first == upper.first + 1 ? lower.second < nums[i] ? make_pair(upper.first + 1, nums[i]) : lower : lower;
            }
            lower = l, upper = u;
        }

        return max(lower.first, upper.first);
    }
};