**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;
}
```