376. Wiggle Subsequence
Description
Soluton
It's easy to link this problem to greedy algorithm or dynamic programming and get the following code.</p>
private static final int UP = 0, DOWN = 1;
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
final int[][] dp = new int[2][nums.length];
dp[0][0] = 1;
dp[1][0] = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i - 1]) {
dp[UP][i] = dp[DOWN][i - 1] + 1;
dp[DOWN][i] = dp[DOWN][i - 1];
} else if (nums[i] < nums[i - 1]) {
dp[DOWN][i] = dp[UP][i - 1] + 1;
dp[UP][i] = dp[UP][i - 1];
} else {
dp[UP][i] = dp[UP][i - 1];
dp[DOWN][i] = dp[DOWN][i - 1];
}
}
return Math.max(dp[UP][nums.length - 1], dp[DOWN][nums.length - 1]);
}
Proof
I was largely inspired by this discussion-dynamic-programming-solution).</p>
In prooving There is no gain in using nums[i] to make a longer subsequence of type D., nums is like the following:
nums[i - 2]
\
\ nums[i]
\ /
\ /
\ /
nums[i - 1]
When the author says
(2) Necessarily nums[i] < N, and therefore nums[i-1] < N since nums[i-1] < nums[i]. But this means that we could have used nums[i-1] already to make a longer subsequence of type D.
It's proving even using nums[i] won't get a better type D sequence due to nums[i - 1] < nums[i], which means choosing nums[i - 1] is more wise.