1
class Solution {
2
 public:
3
  int wiggleMaxLength(vector<int> &nums) {
4
    vector<vector<int>> dp(2, vector<int>(nums.size(), 0));
5
    int ans = 1, high, low;
6
    dp[0][0] = dp[1][0] = 1;
7
    for (int i = 1; i < nums.size(); ++i) {
8
      high = low = 0;
9
      for (int j = 0; j < i; ++j) {
10
        if (nums[i] > nums[j])
11
          low = max(low, dp[1][j]);
12
        else if (nums[i] < nums[j])
13
          high = max(high, dp[0][j]);
14
      }
15
      dp[0][i] = low + 1;
16
      dp[1][i] = high + 1;
17
      ans = max({ans, dp[0][i], dp[1][i]});
18
    }
19
    return ans;
20
  }
21
};