Not Clean but O(N) Solution in Python using DP beating 90%


  • 0
    U
    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if not nums:
                return 0
                
            positive_length = 1
            negative_length = 1
            positive_val = nums[0]
            negative_val = nums[0]
            
            index = 1
            while index < len(nums):
                temp_negative_length, temp_positive_length = -1, -1
                
                if nums[index] - positive_val < 0:
                    temp_negative_val = nums[index]
                    temp_negative_length = positive_length + 1
                    
                if nums[index] - negative_val > 0:
                    temp_positive_val = nums[index]
                    temp_positive_length = negative_length + 1
                    
                if temp_negative_length == negative_length:
                    negative_val = min(negative_val, temp_negative_val)
                elif temp_negative_length > negative_length:
                    negative_length = temp_negative_length
                    negative_val = temp_negative_val
                    
                if temp_positive_length == positive_length:
                    positive_val = max(positive_val, temp_positive_val)
                elif temp_positive_length > positive_length:
                    positive_length = temp_positive_length
                    positive_val = temp_positive_val
                    
                index += 1
            
            return max(positive_length, negative_length)
            
    

Log in to reply
 

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