动态规划-376.摆动序列-力扣(LeetCode)

一、题目解析

看着题目上的解释或许有点难以理解，这里一图流

只要形似上图的都可以是摆动序列，如左图，且仅含一个元素和两个元素的也算摆动序列，如右图

二、算法原理

1、状态表示

根据经验我们都是以i位置为结尾时，最长摆动子序列的长度

但是根据我们下面的题目分析，我们可以知道最后一个位置存在两种情况

f[i]表示：以i位置为结尾时，最后一个呈“上升”趋势的，最长摆动子序列

g[i]表示：一i位置为结尾时，最后一个呈“下降”趋势的，最长摆动子序列

2、状态转移方程

f[i]是以上升为结尾，所以前一个状态为下降

f[i]->长度为1时->f[i]=1

f[i]->长度大于1是->nums[j]<nums[i]，j属于[0,i-1]->f[i]=max(g[j]+1,f[i])

g[i]同理，前一个状态为上升

g[i]->长度为1时->g[i]=1

g[i]->长度大于1是->nums[j]>nums[i]，j属于[0,i-1]->g[i]=max(f[j]+1,g[i])

3、初始化

由于最坏的情况下，所有子序列都为1，所以可以将f、g表内的值全部初始化为1，同时也能处理部分长度为1的情况

4、填表顺序

从左往右，两个表一起填

5、返回值

f_max：f表中的最大值，g_max：g表中的最大值

需要返回两者的最大值

思考过后，去动手实践，趁热打铁，链接：376. 摆动序列 - 力扣（LeetCode）

三、代码示例

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

看到最后，如果对您有所帮助，还请点赞、收藏和关注，点点关注不迷路，我们下期再见！