My DP O(N^2) and Greedy O(N) solution with explanation


  • 0
    B

    DP:
    just like finding longest subsequence in an array, we need using nums[i] to compare with the element showing before them nums[j]. if nums[i] > nums[j] then biggest longest subsequence with ending i equal to :
    max( longest_subsequence(i), longest_subsequence(j+1))
    But in there we have two situations, nums[i] either can be bigger then nums[j] or smaller then nums[j], so we need two DP array to save our result
    the formula is following :
    pos[i] = max(pos[i],neg[j]+1) : if nums[i] > nums[j]
    neg[i] = max(neg[i],pos[j]+1) : if nums[i] < nums[j]

    code:

    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            
            if not nums: return 0
            pos , neg = [1 for i in nums], [1 for i in nums]
            for i in xrange(1,len(nums)):
                for j in xrange(0,i):
                    if nums[i] > nums[j]:
                        neg[i] = max(neg[i],pos[j]+1)
                    elif nums[i] < nums[j]:
                        pos[i] = max(pos[i],neg[j]+1)
            return max(max(pos),max(neg))
    

    Greedy:
    we discuss the problem by two different cases: Wiggle is starting with positive changing ex: [1,3,2] or negative changing ex: [3,1,2]
    if we start as [1,3,2]:
    if we meet the number greater than 2 such as 4 ,our list will become [1,3,2,4].
    if we meet the number smaller than 2 such as 1 ,our list will become [1,3,1].
    the same situation if we start as [3,1,2]
    at the end, we just need to get the biggest element in this two situation

    code as follows:

    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums: return 0
            flag = 1
            cnt = 1
            def count(flag):
                tmp = nums[0]
                cnt = 1
                for i in xrange(1,len(nums)):
                    if tmp < nums[i]:
                        if flag == 1:
                            flag = -1;
                            cnt += 1
                    elif tmp > nums[i]:
                        if flag == -1:
                            flag = 1
                            cnt += 1
                    tmp  = nums[i]
                return cnt
            return max(count(1),count(-1))
    

Log in to reply
 

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