376. 摆动序列
Desciption
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。 给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例：
输入: [1,7,4,9,2,5]
输出: 6
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
Solution
贪心
- 假设整数序列数组为nums，最长子序列数组为seq，考虑第一个整数要不要选。如果seq数组第一个差是正数的话，即seq[0] < seq[1]，则说明nums[0] <= seq[0]（如果nums[0] > seq[0]，则说明可以nums[0]可以加进去组成更长的seq数组），nums[0] 其实可以代替第一个seq[0]；同理，如果seq数组第一个差是负数的话，nums[0] 也可以代替第一个seq[0]。说明nums[0]，肯定在最长子序列数组里
- 接下来只要找第一个差是正数和第一个差是负数的最长答案，看哪一个更长。贪心选择，假设当前的最长子序列最后一个数的值是val，且它上一个差是正数，当前遍历到nums[i]：如果nums[i] > val，则用nums[i]替代val，因为接下来肯定是找差是负数的，所以val越大越好；如果nums[i] < val，则答案长度加1，更新val的值
Code
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 0) {
return 0;
}
int ans = getMaxLen(nums, 1);
ans = Math.max(ans, getMaxLen(nums, 0) + 1);
return ans;
}
private int getMaxLen(int[] nums, int len) {
int val = nums[0];
for (int i = 1; i < nums.length; ++i) {
if (len % 2 == 1) {
if (nums[i] > val) {
val = nums[i]; ++len;
} else {
val = nums[i];
}
} else {
if (nums[i] < val) {
val = nums[i]; ++len;
} else {
val = nums[i];
}
}
}
return len;
}