376. Wiggle Subsequence

我覺得跟714. Best Time to Buy and Sell Stock with Transaction Fee有點異曲同工之妙,

兩著的做法就是交替的感覺,這種dp的skill還蠻難的XD

我們紀錄兩個array, up, down

up 負責記錄最後一個間隔差值為正的情況下, 最長的長度

down負責記錄最後一個間隔差值為負的情況下, 最長的長度

我們從i = 1遍歷整個數列

當nums[i] < nums[i -1]

代表最後一個間隔值為正, 所以up 值為上一個down的值加一

當nums[i] > nums[i -1]

剛好就反過來, down值為上個up值加一

當nums[i] == nums[i -1]

就直接將後面的值往前跟新即可

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
          int size = nums.size();
          if (size == 0)
            return 0;
          vector<int> up(size, 0);
          vector<int> down(size, 0);
          up[0] = 1;
          down[0] = 1;
          for (int i = 1; i < size; 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 {
              down[i] = down[i - 1];
              up[i] = up[i - 1];
            }
          }
          return max(down.back(), up.back());
    }
};

這寫出來反而覺得異常簡單？ 但要從零到這邊我覺得沒接觸過還是有點難度在