# 2 solutions & Proof of O(N) greedy algorithm

• First solution: dynamic programming
we keep 2 arrays:
inc[i] - longest wiggle sequence ending increasing at position i
dec[i] - longest wiggle sequence ending decreasing at position i
There is a good tutorial for this problem, you can check it here:
http://www.hiredintech.com/algorithm-design/idea-generation/
Time: O(N^2), Space: O(N)

Code:

public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] inc = new int[n];
int[] dec = new int[n];
int best = 1;

Arrays.fill(inc, 1);
Arrays.fill(dec, 1);

for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] < nums[j]) {
// decreasing from j
dec[i] = Math.max(dec[i], inc[j] + 1);
} else if (nums[i] > nums[j]) {
// increasing from j
inc[i] = Math.max(inc[i], dec[j] + 1);
}
}
best = Math.max(dec[i], inc[i]);
}
return best;
}

Second solution: greedy
One key observation of the problem is:
No matter where your longest wiggle sequence ends, it can always start from position 0. Why? Here is a proof by contradiction:
Suppose you can not find the longest wiggle sequence starting at position 0, then it must start at some position i, where i > 0. There are three cases:
Case 1: nums[i] > nums[0]
Case 2: nums[i] < nums[0]
Case 3: nums[i] = nums[0]
In all above three cases, you can safely extend the start of your longest wiggle sequence to position 0. You will at least achieve the same length if not better.

Therefore, we can start from position 0 and keep tracking of 3 things:
boolean isIncreasing - is current subsequence increasing or decreasing
curMin - if decreasing, the minimum value of the current decreasing sequence
curMax - if increasing, the maximum value of the current increasing sequence

In my code below, I tried to find the first increasing or decreasing instance to initialize isIncreasing, curMin and curMax, and then perform the greedy approach. Code is kind of lengthy, can be further improved somehow i think.

One last question to think about: are the above 2 approach still working if we define the wiggle sequence as "strictly alternate or equal"?

public static int wiggleMaxLength2(int[] nums) {
// try an greedy approach O(N) time complexity
int n = nums.length;
if (n == 0) {
return 0;
}
int best = 1;
int curMin = nums[0];
int curMax = nums[0];

// find the first increasing or decreasing
boolean isIncreasing = false;
int startIdx = 0;
while (startIdx < n) {
if (nums[startIdx] > nums[0]) {
// find increasing
isIncreasing = true;
best = 2;
curMax = nums[startIdx];
break;
} else if (nums[startIdx] < nums[0]) {
// find decreasing
isIncreasing = false;
best = 2;
curMin = nums[startIdx];
break;
} else {
startIdx += 1;
}
}

for (int i = startIdx + 1; i < n; i++) {
if (isIncreasing) {
if (nums[i] > curMax) {
curMax = nums[i];
} else if (nums[i] < curMax) {
best += 1;
isIncreasing = false;
curMin = nums[i];
}
} else {
if (nums[i] < curMin) {
curMin = nums[i];
} else if (nums[i] > curMin) {
best += 1;
isIncreasing = true;
curMax = nums[i];
}
}
}
return best;
}

• @lzb700m Good proof, but not very detail for case 1,2,3. Anyway I understand now.
Thank you so much.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.