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


  • 34

    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));
        }
    };
    

  • 0

    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);
        }
    };
    

  • 0

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


  • 1
    M

    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);
    }
    }

  • 6
    C

    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]);
    }
    

    ...


  • 0

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


  • 0
    C

    @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?


  • 0

    @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.


  • 0
    H

    such a brief solution! excellent


  • 0
    Z
    This post is deleted!

  • 1
    Z

    @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]?


  • 2

    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); 
        }

  • 0
    S

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

  • 0

    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?


Log in to reply
 

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