AlgoPressAppearance
0376-摆动序列
https://leetcode.cn/problems/wiggle-subsequence
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。 子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1：
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2：
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3：
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
基本思路
参考 0300 最长递增子序列的思路， dp[i] 表示选中这个数字后的最大摆动序列
因为下一个数是要判断上升或者下降，所以当前dp[i]必须记录是上升是的最大序列，或者下降时候的最大序列，有两个状态 dp[i,2]
dp[i,0] 表示当前是上升的最大子序列， dp[i,1]表示当前是下降的最大子序列
状态转移方程如下
如果 nums[j] > nums[i] 则 dp[i,1] = max(dp[i,1],dp[j,0]+1)
如果 nums[j] < nums[i] 则 dp[i,0] = max(dp[i,0],dp[j,1]+1)
参考代码
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
//dp[i,2]表示选中这个数字的最大摆动序列，以及当前的摆动符号
int[,] dp = new int[nums.Length,2];
dp[0,0] = 1; //往上摆动最大序列
dp[0,1] = 1; //往下摆动最大序列
int max = 1;
for(int i=1; i<nums.Length; i++){
dp[i,0] = 1;
dp[i,1] = 1;
for(int j=0; j<i; j++){
if(nums[j] > nums[i]){ //往上
dp[i,1] = Math.Max(dp[i,1],dp[j,0]+1);
if(dp[i,1] > max){
max = dp[i,1];
}
}
else if(nums[j] < nums[i]){ //往下
dp[i,0] = Math.Max(dp[i,0],dp[j,1]+1);
if(dp[i,0] > max){
max = dp[i,0];
}
}
}
}
return max;
}
}
基本思路2： 官方动态规划
定义 up 和 down 数组，up[i] , down[i] 表示到目前为止最大的摆动长度
如果 nums[i] > nums[i-1] , up[i] = down[i-1]+1, down[i] = down[i-1]
如果 nums[i] < nums[i-1], down[i] = up[i-1]+1, up[i] = up[i-1]
csharp
public class Solution{
public int WiggleMaxLength(int[] nums) {
int n = nums.Length;
int[] up = new int[n];
int[] down = new int[n];
up[0] = 1;
down[0] = 1;
for(int i=1; i<n; i++){
if(nums[i] > nums[i-1]) {
up[i] = down[i-1]+1;
down[i] = down[i-1];
}
else if(nums[i] < nums[i-1]){
up[i] = up[i-1];
down[i] = up[i-1]+1;
}
else{
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return Math.Max(up[n-1],)
}
}
思路3：优化空间
up 和 down 之和前一个状态有关，所以只需要保持前一个变量即可。
对 up 和 down 没有操作的时候，就相当于执行了 down[i] = down[i-1] 和 up[i] = up[i-1]
csharp
public class Solution{
public int WiggleMaxLength(int[] nums){
int up = 1;
int down = 1;
for(int i=1; i<nums.Length; i++){
if(nums[i] > nums[i-1]){
up = down + 1;
}
else if(nums[i] < nums[i-1]){
down = up + 1;
}
}
return nums.Length == 0 ? 0 : Math.Max(down,up);
}
}
思路3：贪心算法
计算当前的差值，和前一次的差值。 当 当前的差值 和前一组的差值相反，则可以计算一次波动，否则就跳过。
csharp
public class Solution{
public int WiggleMaxLength(int[] nums){
int preDiff = 0;
int curDiff = 0;
int result = 1;
for(int i=1; i<nums.Length; i++){
curDiff = nums[i] - nums[i-1];
if(curDiff > 0 && preDiff <=0 || curDiff < 0 && preDiff >=0){
result++;
preDiff = curDiff;
}
}
return result;
}
}
复习动归：20220513
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
//动态规划定义两个数组 up 和 down
int n = nums.Length;
int[] up = new int[n];
int[] down = new int[n];
up[0] = 1;
down[0] = 1;
for(int i=1; i<nums.Length; i++){
if(nums[i] > nums[i-1]){
up[i] = down[i-1]+1;
down[i] = down[i-1];
}
else if(nums[i] < nums[i-1]){
down[i] = up[i-1]+1;
up[i] = up[i-1];
}
else{
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return Math.Max(up[n-1],down[n-1]);
}
}
复习贪心：20220513
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
int preDiff = 0;
int curDiff = 0;
int count = 1;
for(int i=1; i<nums.Length; i++){
curDiff = nums[i] - nums[i-1];
if(preDiff <=0 && curDiff >0 || preDiff >=0 && curDiff < 0){
count++;
preDiff = curDiff;
}
}
return count;
}
}
复习：20220620
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
//动态规划，设置 up/down 两个数组记录最大的摆动长度
int n = nums.Length;
int[] up = new int[n];
int[] down = new int[n];
//初始化，第一个默认为1
up[0] = 1;
down[0] = 1;
for(int i=1; i<n; i++){
if(nums[i] > nums[i-1]){
up[i] = down[i-1]+1;
down[i] = down[i-1];
}
else if(nums[i] < nums[i-1]){
up[i] = up[i-1];
down[i] = up[i-1]+1;
}
else{
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return Math.Max(up[n-1],down[n-1]);
}
}
因为 up/down 只和前面一个数有关，所以可以把数组简化
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
//动态规划，设置 up/down 两个数组记录最大的摆动长度
int n = nums.Length;
//初始化，第一个默认为1
int up = 1;
int down = 1;
for(int i=1; i<n; i++){
if(nums[i] > nums[i-1]){
up = down + 1;
}
else if(nums[i] < nums[i-1]){
down = up + 1;
}
}
return Math.Max(up,down);
}
}
贪心算法：注意 preDiff 和 curDiff 的取值和对于0的处理
csharp
public class Solution {
public int WiggleMaxLength(int[] nums) {
int result = 1; //因为数组至少一个，所以默认值是1
//计算每次的差值
int preDiff = 0;
int curDiff = 0; //初始没有变动，差值为0
for(int i=1; i<nums.Length; i++){ //从1开始计算，因为0已经计算了 result = 1
curDiff = nums[i] - nums[i-1];
if(preDiff >=0 && curDiff <0 || preDiff <=0 && curDiff>0){ //这里计算摆动，curDiff==0 这种情况就是跳到下一次计算
result++;
preDiff = curDiff;
}
}
return result;
}
}