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).
1#include <vector>
2#include <iostream>
3using namespace std;
4
5int wiggleMaxLength(vector<int>& nums) {
6 if (nums.size() < 2) return nums.size();
7 int up = 1, down = 1;
8 for (int i = 1; i < nums.size(); i++) {
9 if (nums[i] > nums[i - 1])
10 up = down + 1;
11 else if (nums[i] < nums[i - 1])
12 down = up + 1;
13 }
14 return max(up, down);
15}
16
17int main() {
18 vector<int> nums = {1, 7, 4, 9, 2, 5};
19 cout << wiggleMaxLength(nums) << endl;
20 return 0;
21}The implementation in C++ leverages a similar approach, using a vector to store the input numbers. Keeping track of ascending and descending sequences with up and down variables lets us decide when to extend our potential subsequence by comparing 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
This approach makes use of two additional arrays up and down which are dynamically allocated to store the longest wiggle subsequence lengths. For each element, it checks all previous elements to update up and down arrays.