Today's Challenge

https://leetcode.com/problems/wiggle-subsequence/

Wiggle Subsequence - LeetCode

문제를 푸는 방법이 매우 여러 가지다.
완전 탐색, DP, LIS,..
그중에 내가 참고한 솔루션은 변곡점을 구하는 방식을 사용한다.
다른 알고리즘에 비해 꽤나 신박한 느낌이었다. =_=

그런데 수행 결과가 그렇게 빠르지는 않다. 왜 일까?

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        high, low = 1, 1
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                high = low + 1
            elif nums[i-1] > nums[i]:
                low = high + 1
        return max(high, low)