Short and easy to understand Python solution with explanation


  • 0
    G

    Key ideas: At least one of the longest subsequences will start with the first element. For all increasing and decreasing subarrays, ignore duplicates and acknowledge only their first and last elements.

    Example:
    nums = [1, 3, 4, 4, 5, 2, 6, -1, 0, 1]
    increasing subarray [1, 3, 4, 4, 5]: we only care about the 1 and 5
    decreasing subarray [6, -1, 0]: we only care about the 6 and 0
    longest subsequence: [1, 5, 2, 6, 0, 1]

    Maintain two booleans to know whether the next element should increase or decrease. Maintain previous element to compare and determine if current element is valid.

    def wiggleMaxLength(self, nums):
        if len(nums) < 2:
            return len(nums)
            
        incr, decr = False, False
        prev = nums[0]
        count = 1
        for num in nums[1:]:
            if num > prev and not decr:
                count += 1
                incr, decr = False, True
            elif num < prev and not incr:
                count += 1
                decr, incr = False, True
            prev = num
        return count

Log in to reply
 

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