LeetCode 376. 摆动序列

最长递增子序列

题目链接:

376. 摆动序列

题目描述:

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 **摆动序列 。**第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

题目解析

这道题目理解还是有一点困难的.我们先说一下摆动序列的定义, 下面每一个数字可以理解为两个数的差.

如果我们数组的一个元素减去前面的一个元素构成上面这种一正一负的情况,我们把这个数组称之为摆动序列.

算法原理

我们还是按照我们的一般的经验来解决这个问题

• 以…为结尾

状态表示

这里我们定义下面的状态

dp[i] : 表示以i位置为结尾的我们的摆动序列的最大的长度
1

当时我们依照上面的来实现状态转移方程的时候,此时出现两个状态

• 差值为 正数
• 差值 为 负数

所以这里是多状态的.

f[i]: 表示以i位置为结尾, 我们差值为正值的摆动序列的最大长度
g[i]: 表示以i位置为结尾, 我们差值为负值的摆动序列的最大长度
1
2

状态转移方程

在进行状态转移方程的计算的时候,我们首先要计算我们的差值

1.如果差值是正数
    1.1 更新 f[i] = g[i-1] + 1 ,这是因为需要和前面的差值是负数打配合
    1.2 更新 g[i] = g[i-1]     ,g[i] 不需要变换
2.如果差值是负数
    2.1 更新 g[i] = f[i-1] + 1 , 和正数打配合
    2.2 更新 f[i] = f[i-1]
3.如果差值是0
    3.1 更新 g[i] = g[i-1]
    3.2 更新 f[i] = f[i-1]
1
2
3
4
5
6
7
8
9

初始化

这里我们看到题目有一个很重要的说法,他说如果单独一个元素,那么我们也是摆动序列.也就是

f[0] = 1
g[0] = 1
1
2

填表顺序

从左向右填,两个表一起走.

返回值

返回我们的两个数组最后的较大值就可以了.注意,有的时候我们返回值拿一个变量保存最大值,有的时候返回我们的最后一个元素,这里我们不做记忆,可以看我们的例子来具体的使用那个.

编写代码

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> f(n, 1);
        vector<int> g(n, 1);
        for(int i = 1; i < nums.size(); ++i)
        {
            int ret = nums[i] - nums[i-1];
            if(ret > 0)
            {
                f[i] = g[i-1]+1;
                g[i] = g[i-1];
            }   
            else if(ret < 0)
            {
                g[i] = f[i-1]+1;
                f[i] = f[i-1];
            }   
            else 
            {
                f[i] = f[i-1];
                g[i] = g[i-1];
            }  
        }
        return max(f.back(), g.back());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29