# Java O(n) greedy solution

• ``````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;
}
}``````

• Do you really need `max`? I think you can just return `count`.

• @StefanPochmann You are right, will update it, thanks.

• Can you explain why this works?

I tried your solution on this [1,17,5,10,13,15,10,5,16,8] and it returned:
1 17 5 10 10 16 18

• @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 as `int[] res` .
Suppose you've already got `res[j - 1] > res[j - 2]`, which means `prevInc == true`, now you need a decreasing number to get the longest subsequence. If you get an increasing number now, you need to update `res[j - 1]` with `num[i]`. Because the bigger your `res[j - 1]` is, the easier you can find a `res[j] < res[j - 1]` .

• @qianzhige

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 8

I'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[i-1] (you may also need to print nums[i] as the last element, if you reach the end of the input sequence).

• Boolean prevInc

The way to use boolean flag is fantastic !

• I used DP to get an O(n^2) solution because I could not convinced myself that greedy solution will work. Why short-sightedness of greedy algorithm will not apply to this problem? Do you have a general idea about when to be greedy?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.