O(n^2) DP and O(n) Greedy solution


  • 0

    Comments tell the idea.

    class Solution(object):
        # O(n^2) DP dp[i] => subsequence ends at nums[i] (nums[i] included)
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            dp = [1 for _ in range(len(nums))]
            dp1 = [1 for _ in range(len(nums))]
            ans = 1
            for i in xrange(1, len(nums)):
                for j in xrange(0, i):
                    if dp[j] % 2 == 0 and nums[i] < nums[j]:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if dp[j] % 2 == 1 and nums[i] > nums[j]:
                        dp[i] = max(dp[i], dp[j] + 1)
                    if dp1[j] % 2 == 0 and nums[i] > nums[j]:
                        dp1[i] = max(dp1[i], dp1[j] + 1)
                    if dp1[j] % 2 == 1 and nums[i] < nums[j]:
                        dp1[i] = max(dp1[i], dp1[j] + 1)
                ans = max(ans, dp[i], dp1[i])
            return ans if len(nums) else 0
            
        # Greedy: count turning points and ignore monotonic areas
    
        def wijggleMaxLength(self, nums):
            mono = None
            ans = 1
            for i in xrange(1, len(nums)):
                diff = nums[i] - nums[i - 1]
                if diff == 0: continue
                if (not mono) or (mono and diff * mono < 0):
                    ans += 1
                    mono = diff
            return ans if len(nums) else 0
    

Log in to reply
 

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