动态规划-子序列问题——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;}
};