python dp and greedy


  • 0
    T
    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            return self.greedy(nums)
            return self.dp(nums)
        
        # O(n)
        def greedy(self,nums):
            size = len(nums)
            if size <= 1:
                return size
            mono = None
            cnt = 1
            for i in xrange(1,size):
                diff = nums[i]-nums[i-1]
                if diff == 0:
                    continue
                if not mono or diff*mono<0:
                   mono = diff
                   cnt += 1
            return cnt
        
        # O(n^2)
        def dp(self,nums):
            size = len(nums)
            if size <= 1:
                return size
            sml,big = [1]*size,[1]*size
            for i in xrange(0,size):
                for j in xrange(0,i):
                    if nums[i] > nums[j]:
                        big[i] = max(big[i],sml[j]+1)
                    elif nums[i] < nums[j]:
                        sml[i] = max(sml[i],big[j]+1)
            return max(max(sml),max(big))
    

Log in to reply
 

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