力扣No.376.摆动序列

题目：

链接：

https://leetcode.cn/problems/wiggle-subsequence/description/

代码：

class Solution {public int wiggleMaxLength(int[] nums) {int n=nums.length;//状态表示:int[] f=new int[n];int[] g=new int[n];//初始化:for(int i=0;i<n;i++) f[i]=g[i]=1;int ret=1;//转移方程:for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(nums[i]>nums[j]) f[i]=Math.max(f[i],g[j]+1);else if(nums[i]<nums[j]) g[i]=Math.max(g[i],f[j]+1);}ret=Math.max(ret,Math.max(f[i],g[i]));}//返回值:return ret;}
}

动态规划思路

动态规划题可以从以下5方面去思考：

• 状态表示
• 转移方程
• 初始化
• 填表顺序
• 返回值

状态表示的意思是：创建的数组的含义是什么；

转移方程的意思是：创建的数组满足什么关系；

初始化是：创建的数组初始为什么值才能保证满足题意且不越界；

填表顺序是：从哪里开始遍历数组；

返回值是：最终返回的结果是什么。

解题过程：

题中要求子序列的三个数字直接差值为正负交替出现.我们可以想到两个数字的差值无非是大于0与小于0和等于0.

由于题中要求严格递增.所以等于0不考虑.我们只需要考虑大于0和小于0.

我们把大于0看作上升趋势,即nums[i]>nums[j];把小于0看作下降趋势,即nums[i]<nums[j];

那么摆动序列就是上升趋势的下一个是下降趋势.下降趋势的下一个是上升趋势.所以这道题可以看作是动态规划中的多状态问题.

状态表示:[i]和g[i].

f[i]表示:以下标i结尾的子序列中,最大的摆动序列的长度,且最后到nums[i]为上升趋势;

g[i]表示:以下标i结尾的子序列中,最大的摆动序列的长度,且最后到nums[i]为下降趋势;

转移方程:

当长度=1时,f[i]=g[i]=1;

当长度>1时,如果(nums[i]>nums[j]) 即:f[i]=Math.max(f[i],g[j]+1);

如果(nums[i]<nums[j]) 即: g[i]=Math.max(g[i],f[j]+1);

初始化:

因为f和g最小值为1,所以令f和g的元素都为1.

填表顺序:

从左到右.

返回值:

返回f[i]和g[i]中的最大值,可以用ret表示.