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 <stdio.h>
2
3int wiggleMaxLength(int* nums, int numsSize){
4 if(numsSize < 2) return numsSize;
5 int up = 1, down = 1;
6 for(int i = 1; i < numsSize; ++i) {
7 if(nums[i] > nums[i-1])
8 up = down + 1;
9 else if(nums[i] < nums[i-1])
10 down = up + 1;
11 }
12 return (up > down) ? up : down;
13}
14
15int main() {
16 int nums[] = {1, 7, 4, 9, 2, 5};
17 int length = sizeof(nums) / sizeof(nums[0]);
18 printf("%d\n", wiggleMaxLength(nums, length));
19 return 0;
20}The function wiggleMaxLength takes an array nums and its size. It uses two pointers up and down initialized as 1 representing the length of the longest subsequence. Loop through each element, and check if it's larger or smaller than the previous one, updating up and down appropriately. The final result is the maximum of these two values.
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
public class Solution {
public int WiggleMaxLength(int[] nums) {
if (nums.Length < 2) return nums.Length;
int[] up = new int[nums.Length];
int[] down = new int[nums.Length];
Array.Fill(up, 1);
Array.Fill(down, 1);
for (int i = 1; i < nums.Length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
up[i] = Math.Max(up[i], down[j] + 1);
else if (nums[i] < nums[j])
down[i] = Math.Max(down[i], up[j] + 1);
}
}
return Math.Max(up[nums.Length - 1], down[nums.Length - 1]);
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 7, 4, 9, 2, 5};
Console.WriteLine(sol.WiggleMaxLength(nums));
}
}In C#, this dynamic programming approach utilizes two arrays up and down to track subsequence lengths, analyzing each elements relationship to previous elements to determine growth in subsequence length.