public class Solution {
public int wiggleMaxLength(int[] nums) {
if(nums.length <= 1) return nums.length;
int count = 1;
Boolean prevInc = null;
for(int i = 1; i < nums.length; i++) {
if(nums[i] > nums[i  1] && (prevInc == null  !prevInc)) {
prevInc = true;
count++;
} else if(nums[i] < nums[i  1] && (prevInc == null  prevInc)) {
prevInc = false;
count++;
}
}
return count;
}
}
Java O(n) greedy solution



@quincyhehe
for[1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
,
my solution should return:[1, 17, 5, 15, 5, 16, 8]
.
To better explain the idea, let's name the result array asint[] res
.
Suppose you've already gotres[j  1] > res[j  2]
, which meansprevInc == true
, now you need a decreasing number to get the longest subsequence. If you get an increasing number now, you need to updateres[j  1]
withnum[i]
. Because the bigger yourres[j  1]
is, the easier you can find ares[j] < res[j  1]
.

Thank you very much for your reply.
I tried this
public static int wiggleMaxLength(int[] nums) { if(nums.length <= 1) return nums.length; int count = 1; Boolean prevInc = null; for(int i = 1; i < nums.length; i++) { if(nums[i] > nums[i  1] && (prevInc == null  !prevInc)) { System.out.println(nums[i]); prevInc = true; count++; } else if(nums[i] < nums[i  1] && (prevInc == null  prevInc)) { System.out.println(nums[i]); prevInc = false; count++; } } return count; }
and the printed number is:
17 5 10 10 16 8I'm very confused.

@quincyhehe To get the exact wiggle subsequence, you should always pick the local maximum/minimum. But what you print out is the element next to the local maximum/minimum, so this may be confusing. You should print nums[i1] (you may also need to print nums[i] as the last element, if you reach the end of the input sequence).

@qianzhige said in Java O(n) greedy solution:
Boolean prevInc
The way to use boolean flag is fantastic !