每当我们选择一个元素作为摆动序列的一部分时,这个元素要么是上升的,要么是下降的,这取决于前一个元素的大小。那么列出状态表达式为:
up[i] 表示以前 i个元素中的某一个为结尾的最长的「上升摆动序列」的长度。
down[i] 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。
下面以 up[i] 为例,说明其状态转移规则:
- 当``nums[i]-nums[i-1]
时,我们无法选出更长的「上升摆动序列」的方案。因为对于任何以
nums[i]`结尾的「上升摆动序列」,我们都可以将 nums[i] 替换为nums[i−1],使其成为以nums[i−1] 结尾的「上升摆动序列」。 - 当nums[i]>nums[i−1] 时,我们既可以从up[i−1] 进行转移,也可以从down[i−1] 进行转移。下面我们证明从 down[i−1] 转移是必然合法的,即必然存在一个down[i−1] 对应的最长的「下降摆动序列」的末尾元素小于nums[i]。
们记这个末尾元素在原序列中的下标为 jj,假设从 jj 往前的第一个「谷」为nums[k],我们总可以让 jj 移动到 kk,使得这个最长的「下降摆动序列」的末尾元素为「谷」。
然后我们可以证明在这个末尾元素为「谷」的情况下,这个末尾元素必然是从nums[i] 往前的第一个「谷」。证明非常简单,我们使用反证法,如果这个末尾元素不是从nums[i] 往前的第一个「谷」,那么我们总可以在末尾元素和nums[i] 之间取得一对「峰」与「谷」,接在这个「下降摆动序列」后,使其更长。
这样我们知道必然存在一个down[i−1] 对应的最长的「下降摆动序列」的末尾元素为nums[i] 往前的第一个「谷」。这个「谷」必然小于nums[i]。证毕。
class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length<2) return nums.length;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
up[0] = 1;
down[0] = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
up[i] = up[i - 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 if (nums[i] > nums[i - 1]) {
down[i] = down[i - 1];
up[i] = Math.max(up[i - 1], down[i - 1] + 1);
}
}
return Math.max(up[nums.length - 1], down[nums.length - 1]);
}
}