擺動序列

題目鏈接

• 貪心
  盡可能多的選擇波峰波谷。

class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2) {return n;}int pre = nums[1] - nums[0];int ret = pre == 0 ? 1 : 2;for (int i = 2; i < n; ++i) {int diff = nums[i] - nums[i-1];if ((diff > 0 && pre <= 0) || (diff < 0 && pre >= 0)) {pre = diff;++ret;}}return ret;} };

• 動態規劃
  up[ i ] = 前i個元素最長的上升擺動序列（結尾為上升）
  down[ i ] = 前i個元素最長的下降擺動序列（結尾為下降）

class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2) {return n;}vector<int> up(n, 0), down(n, 0);up[0] = down[0] = 1;for (int i = 1; i < n; ++i) {if (nums[i] > nums[i-1]) {up[i] = max(up[i-1], down[i-1] + 1);down[i] = down[i-1];}else if (nums[i] < nums[i-1]){up[i] = up[i-1];down[i] = max(down[i-1], up[i-1] + 1);}else {up[i] = up[i-1];down[i] = down[i-1];}}return max(up[n-1], down[n-1]);} }; class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2) {return n;}int up = 1, down = 1;for (int i = 1; i < n; ++i) {if (nums[i] > nums[i-1]) {up = max(up, down + 1);}else if (nums[i] < nums[i-1]){down = max(down, up + 1);}}return max(up, down);} }; 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的贪心/动态规划 - 摆动序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。