Sponsored
Sponsored
In this approach, we maintain a greedy solution by keeping track of directions of the growing and shrinking sequences. We scan through the array, checking the differences between consecutive numbers. Whenever a change in the sign is detected, it contributes to a count of the longest wiggle sequence.
This approach efficiently computes in O(n) time by scanning the list only once.
Time Complexity: O(n).
Space Complexity: O(1).
1def wiggleMaxLength(nums):
2 if len(nums) < 2:
3 return len(nums)
4 up = down = 1
5 for i in range(1, len(nums)):
6 if nums[i] > nums[i - 1]:
7 up = down + 1
8 elif nums[i] < nums[i - 1]:
9 down = up + 1
10 return max(up, down)
11
12nums = [1, 7, 4, 9, 2, 5]
13print(wiggleMaxLength(nums))The Python solution follows the greedy strategy approach to determine the maximum length of a wiggle subsequence. Using two counters up and down, we iterate through each element and update these counters based on the observed differences.
This solution involves using dynamic programming to keep track of two arrays - up[i] and down[i] where up[i] and down[i] indicate the longest wiggle subsequence ending at index i with an upward or downward difference respectively.
This allows evaluating the longest wiggle subsequence leading to a time complexity of O(n^2), given we evaluate each index pair combination.
Time Complexity: O(n^2).
Space Complexity: O(n).
1
JavaScript implementation similarly relies on arrays up and down for storing the wiggle length at any given index. Each nested iteration compares elements and decides how to maximize the subsequence length appropriately.