Find length of longest wiggle subsequence (alternating up/down differences).
Input: nums=[1,7,4,9,2,5] → Output: 6
Input: nums=[1,17,5,10,13,15,10,5,16,8] → Output: 7
Greedy: count peaks and valleys. Track direction of last counted difference.
- Track up and down counts, both start at 1
- For each pair: if nums[i]>nums[i-1] and last was down: up++
- If nums[i]
- Return max(up, down)
public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;
int up = 1, down = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > nums[i-1]) up = down + 1;
else if (nums[i] < nums[i-1]) down = up + 1;
}
return Math.max(up, down);
}
- Time Complexity: O(n)
- Space Complexity: O(1)