Python DP Solution


  • 0
    W
    class Solution(object):
    
        def wiggleMaxLength(self, nums):
    
            cache = {}
            
            def _dp(i):
                if i == 0:
                    return (1, 1)
                if i in cache:
                    return cache[i]
                    
                n = nums[i]
                rs = [_dp(j) for j in range(i) if nums[j] < n]
                r1 = max(r[0] for r in rs) if rs else 0
                rs = [_dp(j) for j in range(i) if nums[j] > n]
                r2 = max(r[1] for r in rs) if rs else 0
                    
                ret = (r2+1, r1+1)
                cache[i] = ret
                return ret
            
            rs = [r for j in xrange(len(nums)) for r in _dp(j)]
            return max(rs) if rs else 0
    

Log in to reply
 

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