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.

参考代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;
        int up[n] = {0};
        int down[n] = {0};
        
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    up[i] = max(up[i], 1+down[j]);
                }else if(nums[j] > nums[i]){
                    down[i] = max(down[i] , 1+up[j]);
                }else{
                    up[i] = max(up[i], up[j]);
                    down[i] = max(down[i], down[j]);
                }
            }
        }
        
        return max(up[n-1], down[n-1]) + 1;
    }
};

分析

这道题和一般的dp题有点不一样。之前我见过一个1D数组和2D数组来保存状态的DP题，当看到这道题时，也试图以类似的套路去套用，但是却并不成功。

从dp题最基本的思路去思考这个问题，才是解决之道。

首先我们思考如何决定以s[i]为最终字符的子串。

如果s[i] > s[i-1]，那么s[i]，s[i-1]可能在一个最优解中。

如果s[i] > s[i-2]，那么s[i]，s[i-2]也可能在一个最优解中。

…

如果s[i] > s[0]，那么s[i]，s[0]也可能在一个最优解中。

当然s[i] < s[j] 或者s[i] == s[j] , j < i，也可能在最优解中。

对于多种可能的情况，我们就需要compare来决定选取那个为最优解。

  1. 如果s[i] > s[i-1]，显然如果以s[i-1]为最终字符的子串，且该子串中s[i-1]的前驱大于s[i-1],那么该子串长度+1将是一个候选者。
  2. 如果s[i] < s[i-1]，显然如果以s[i-1]为最终字符的子串，且该子串中s[i-1]的前驱小于s[i-1],那么该子串长度+1将是一个候选者。
  3. 如果s[i] == s[i-1]，显然如果以s[i-1]为最终字符的子串，那么该子串长度将是一个候选者。

综合以上三种情况，我们需要知道关于s[i-1]的两个信息，

一个是s[i-1]为最终字符的子串，且该子串中s[i-1]的前驱大于s[i-1]

另一个是以s[i-1]为最终字符的子串，且该子串中s[i-1]的前驱小于s[i-1]

而我们需要的是关于这两个子串的子串长度，于是可以作up[]和down[]两个数组来分别保存对应的状态。

这就是这道DP题不一样的地方，需要两个数组来保存对应的状态，而不是一个，无论他是一维的还是二维的。