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).
1function wiggleMaxLength(nums) {
2 if (nums.length < 2) return nums.length;
3 let up = 1, down = 1;
4 for (let i = 1; i < nums.length; i++) {
5 if (nums[i] > nums[i - 1])
6 up = down + 1;
7 else if (nums[i] < nums[i - 1])
8 down = up + 1;
9 }
10 return Math.max(up, down);
11}
12
13let nums = [1, 7, 4, 9, 2, 5];
14console.log(wiggleMaxLength(nums));JavaScript implementation utilizes two counters, up and down, to keep track of potential wiggle sequences as we iterate through the input array. The counters are updated based on observed trends between consecutive elements.
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#include <iostream>
using namespace std;
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2) return nums.size();
vector<int> up(nums.size(), 1);
vector<int> down(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])
up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])
down[i] = max(down[i], up[j] + 1);
}
}
return max(up.back(), down.back());
}
int main() {
vector<int> nums = {1, 7, 4, 9, 2, 5};
cout << wiggleMaxLength(nums) << endl;
return 0;
}The C++ implementation uses vectors up and down to dynamically store subsequence lengths for each point. As each pair is checked, the vectors are updated based on the conditions of increase or decrease.