흔들기 하위 시퀀스

흔들기 시퀀스는 연속된 숫자 간의 차이가 양수와 음수 사이에서 엄격하게 번갈아 나타나는 시퀀스입니다. 첫 번째 차이(존재하는 경우)는 양수 또는 음수일 수 있습니다. 하나의 요소가 있는 시퀀스와 두 개의 동일하지 않은 요소가 있는 시퀀스는 trivially wiggle 시퀀스입니다.

예를 들어 [1, 7, 4, 9, 2, 5]는 차이(6, -3, 5, -7, 3)가 양수와 음수 사이에서 번갈아 나타나기 때문에 위글 시퀀스입니다.

반대로 [1, 4, 7, 2, 5] 및 [1, 7, 4, 5, 5]는 흔들기 시퀀스가 ​​아닙니다. 첫 번째는 처음 두 차이가 양수이기 때문이 아니며 두 번째는 마지막 차이가 0이기 때문이 아닙니다.

하위 시퀀스는 원래 시퀀스에서 일부 요소(아마도 0)를 삭제하고 나머지 요소는 원래 순서대로 남겨 두어 얻습니다.

정수 배열 nums 이 주어지면 nums 의 가장 긴 흔들기 하위 시퀀스의 길이를 반환합니다.

예 1:

입력: 숫자 = [1,7,4,9,2,5]
출력: 6
설명: 전체 시퀀스는 차이(6, -3, 5, -7, 3)가 있는 흔들기 시퀀스입니다.

예 2:

입력: 숫자 = [1,17,5,10,13,15,10,5,16,8]
출력: 7
설명: 이 길이를 달성하는 여러 하위 시퀀스가 ​​있습니다.
하나는 [1, 17, 10, 13, 10, 16, 8]이고 차이는 (16, -7, 3, -3, 6, -8)입니다.

예 3:

입력: 숫자 = [1,2,3,4,5,6,7,8,9]
출력: 2

제약:

1 <= nums.length <= 1000

0 <= nums[i] <= 1000

후속 조치: O(n) 시간 내에 이 문제를 해결할 수 있습니까?

해결책:

class Solution:
    def maxWig(self, nums, i, n, inc):
        if (i, inc) in self.cache:
            return self.cache[(i, inc)]
        maxSeq = 1
        for j in range(i + 1, n):
            if inc:
                if nums[j] > nums[i]:
                    maxSeq = max(maxSeq, 1 + self.maxWig(nums, j, n, False))
            else:
                if nums[j] < nums[i]:
                    maxSeq = max(maxSeq, 1 + self.maxWig(nums, j, n, True))
        self.cache[(i, inc)] = maxSeq
        return maxSeq

    def wiggleMaxLength(self, nums: List[int]) -> int:
        self.cache = {}
        n = len(nums)
        maxSeq = 1
        for i in range(n):
            maxSeq = max(maxSeq, self.maxWig(nums, i, n, True))
            maxSeq = max(maxSeq, self.maxWig(nums, i, n, False))
        return maxSeq