题目链接
题目描述
实现代码
动态规划思想:定义两个数组:up[i] 和 down[i]:
- up[i]:表示前i个元素而言的最后两个元素为递增的最长摆动序列长度
- down[i]:表示前i个元素而言的最后两个元素为递减的最长摆动序列长度
nums[i+1] > nums[i]时更新方式:
up[i+1] = max(up[i], down[i] + 1) down[i+1] = down[i]
nums[i+1] < nums[i]时更新方式:
down[i+1] = max(down[i], up[i] + 1) up[i+1] = up[i]
nums[i+1] == nums[i]时更新方式:
up[i+1] = up[i] down[i+1] = down[i]
最终的结果为:
max(up[n-1], down[n-1])
实现代码:
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
int[] up = new int[n];
int[] down = new int[n];
up[0] = down[0] = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
down[i] = down[i - 1];
} else if (nums[i] < nums[i - 1]) {
up[i] = up[i - 1];
down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
} else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return Math.max(up[n - 1], down[n - 1]);
}
}