Share my short DP O(n^2) c++ solution


  • 1
    S

    I used two arrays to keep track of the length of subsequence that ends with A[i].
    The large[] array keeps track of the subsequence that ends with and A[i] is larger than the previous element. The small[] array keeps track of the subsequence that ends with A[i] and A[i] is smaller than the previous element.

    Here is my solution:

    class Solution {
    public:
        int wiggleMaxLength(vector<int>& nums) {
            if(nums.size() == 0)
                return 0;
            vector<int> large(nums.size(),1);
            vector<int> small(nums.size(),1);
            for(int i=1;i<nums.size();i++){
                for(int j=0;j<i;j++){
                    if(nums[i] > nums[j])
                        large[i] = max(large[i],small[j]+1);
                    if(nums[i] < nums[j])
                        small[i] = max(small[i], large[j]+1);
                }
            }
            return max(*max_element(large.begin(), large.end()), *max_element(small.begin(),small.end()));
        }
    };
    

Log in to reply
 

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