动态规划-子序列问题——376.摆动序列

1.题目解析

题目来源：376.摆动序列——力扣

测试用例

2.算法原理

1.状态表示

以数组第i个位置为例，假设第i个位置为摆动序列的最后一个位置，此时就有两种情况，即最后位置向上摆以及向下摆，所以需要两个表来存储这两种不同的状态

f[i]:以第i个位置为结尾且结尾是上升状态的最长子序列长度

g[i]:以第i个位置为结尾且结尾是下降状态的最长子序列长度

2.状态转移方程

我们一直摆动序列是一上一下的状态，所以在填两个表时需要分别用到对方的前一个位置，即

f[i] = max(g[j]+1,f[i]);g[i]=max(f[j]+1,g[i]);

3.初始化

摆动序列的最小长度为1，那么不妨直接将两个表初始化为全1，这样就不用考虑单个字符成一个序列的情况

4.填表顺序

从左到右，两个表一起填写

5.返回值

返回两个表中的最大值

3.实战代码

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