# Two solutions. One is DP, the other is greedy (8 lines).

• DP:

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size=nums.size();
if(size==0) return 0;
vector<int> f(size, 1);
vector<int> d(size, 1);
for(int i=1; i<size; ++i){
for(int j=0; j<i; ++j){
if(nums[j]<nums[i]){
f[i]=max(f[i], d[j]+1);
}
else if(nums[j]>nums[i]){
d[i]=max(d[i], f[j]+1);
}
}
}
return max(d.back(), f.back());
}
};
``````

Greedy:

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size=nums.size(), f=1, d=1;
for(int i=1; i<size; ++i){
if(nums[i]>nums[i-1]) f=d+1;
else if(nums[i]<nums[i-1]) d=f+1;
}
return min(size, max(f, d));
}
};
``````

• Just make the greedy one shorter:

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int count1 = 1, count2 = 1;
for(int i = 1; i < nums.size(); ++i)
if(nums[i] > nums[i-1]) count1 = count2 + 1;
else if(nums[i] < nums[i-1]) count2 = count1 + 1;
return nums.size() == 0 ? 0 : max(count1, count2);
}
};
``````

• Very nice greedy solution, but your DP solution doesn't look very DP. It's O(n^2) ?

• Thanks for the solutions.

I originally came up with the similar DP idea but not the greedy one. Here are my two Java implementations.

The variable ends_large stores the max length for the subsequence with the current number being larger than the last number in the subsequence. And vice versa for ends_small.

``````// dp solution
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int len = nums.length;
int[] ends_large = new int[len];
int[] ends_small = new int[len];
Arrays.fill(ends_large, 1);
Arrays.fill(ends_small, 1);
for (int i = 1; i < len; i++) {
for (int j = i-1; j >= 0; j--) {
if (nums[i] > nums[j]) ends_large[i] = Math.max(ends_large[i], ends_small[j] + 1);
else if (nums[i] < nums[j]) ends_small[i] = Math.max(ends_small[i], ends_large[j]+1);
}
}
return Math.max(ends_small[len-1], ends_large[len-1]);
}
}

// The greedy solution
public class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) return 0;
int len = nums.length;
int ends_large = 1;
int ends_small = 1;
for (int i = 1; i < len; i++) {
if (nums[i] < nums[i-1]) ends_small = ends_large + 1;
else if (nums[i] > nums[i-1]) ends_large = ends_small + 1;
}
return Math.max(ends_small, ends_large);
}
}``````

• Hi,

I don't quite understand why it is required to have the inner for loop for the DP approach...

I tried to only use one for loop, and seems fine. The following is my code based on metalsolid1's original contribution..... (please, please, please... do NOT give me a negative mark if it is wrong, I only have 2 points left. :( )

...
public int wiggleMaxLength(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

``````    int len = nums.length;
int[] endsSmall = new int[len];
int[] endsLarge = new int[len];

Arrays.fill(endsSmall, 1);
Arrays.fill(endsLarge, 1);

for (int i = 1; i < len; i++) {
if (nums[i] < nums[i - 1]) {
endsSmall[i] = Math.max(endsSmall[i - 1], endsLarge[i - 1] + 1);
endsLarge[i] = endsLarge[i - 1];
}
else if (nums[i] > nums[i - 1]) {
endsLarge[i] = Math.max(endsLarge[i - 1], endsSmall[i - 1] + 1);
endsSmall[i] = endsSmall[i - 1];
}
else {
endsLarge[i] = endsLarge[i - 1];
endsSmall[i] = endsSmall[i - 1];
}
}

return Math.max(endsSmall[len - 1], endsLarge[len - 1]);
}
``````

...

• @chenw2000 I think your code is Greedy. Although it's too long and using two useless vectors.

• @clubmaster Hi, Clubmaster, nice to see you! Thanks for your initiative solution. My question is: if I want to apply the DP approach, is it necessary to keep track of the previous values / results so as to derive the new value / result? Even though that 2 arrays are useless based on your greed algorithm, it is behaves to keep the style of DP...

Another question is: in your DP solution, there is an inner loop for 0 to i to determine the endLarge / endSmall value at position [i], based on your greedy algorithm, seems the value only depends on the nums[i] and nums[i-1]... so I removed the inner loop and add some more checks... but... it is still a DP algorithm?

• @chenw2000 You are correct. It's DP style :). I think you can argue if it's DP or greedy. It's not a zero/one question.

• such a brief solution! excellent

• This post is deleted!

• @chenw2000 Hi can you explain the following highlighted code? Thanks!

if (nums[i] < nums[i - 1]) {
endsSmall[i] = Math.max(endsSmall[i - 1], endsLarge[i - 1] + 1);
`endsLarge[i] = endsLarge[i - 1]; *** Why this?`
}

Since nums[i] < nums[i-1], why endsLarge[i] should = endsLarges[i-1]?

• Greedy:

``````    public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if (n <= 1) return n;

int up = 1, down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) up = down + 1;
if (nums[i] < nums[i - 1]) down = up + 1;
}

return Math.max(up, down);
}``````

• straightforward greedy:

``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
if(n<2) return n;
if(n==2)
{
if(nums[1]==nums[0]) return 1;
else return 2;
}
int res=2;
if(nums[1]==nums[0]) res=1;
int cur = nums[1]-nums[0];
for(int i=2;i<n;i++)
{
int dif = nums[i]-nums[i-1];
if(cur*dif<0 || (cur==0 && dif!=0))
{
res++;
cur=dif;
}
}
return res;
}
};``````

• Hello, I am just a little curious, why the greedy solution above could be counted as an greedy? I mean a greedy consists of greedy choice and optimal substructure,right? But where is the greedy choice?

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