nums라는 숫자 목록이 있다고 가정하고 가장 길게 증가하는 부분 수열의 길이를 찾아야 하고 부분 수열이 목록의 시작 부분으로 줄바꿈할 수 있다고 가정합니다.
따라서 입력이 nums =[6, 5, 8, 2, 3, 4]와 같으면 가장 긴 증가 부분 시퀀스가 [2, 3, 4, 6, 8]이므로 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- a :=숫자의 두 배 크기 목록을 만들고 숫자를 두 번 채우기
- ans :=0
- 0~숫자 크기 범위의 i에 대해
- dp :=새 목록
- i 범위에서 nums + i - 1의 크기까지 j에 대해, do
- n :=a[j]
- k :=dp에 n을 삽입하기 위한 가장 왼쪽 인덱스
- k가 dp의 크기와 같으면
- dp 끝에 n 삽입
- 그렇지 않으면
- dp[k] :=n
- ans :=최대 as 및 dp 크기
- 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
import bisect class Solution: def solve(self, nums): a = nums + nums ans = 0 for i in range(len(nums)): dp = [] for j in range(i, len(nums) + i): n = a[j] k = bisect.bisect_left(dp, n) if k == len(dp): dp.append(n) else: dp[k] = n ans = max(ans, len(dp)) return ans ob = Solution() nums = [4, 5, 8, 2, 3, 4] print(ob.solve(nums))
입력
[4, 5, 8, 2, 3, 4]
출력
5