[LeetCode] 0300. 가장 긴 증가 부분 수열

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

정수 배열이 주어지면 숫자, 반품 길이가 가장 긴 것 엄격하게 증가 후속.

예시 1:

입력: 숫자 = [10,9,2,5,3,7,101,18]
산출: 4
설명: 가장 긴 증가 부분 수열은 [2,3,7,101]이므로 길이는 4입니다.

예 2:

입력: 숫자 = [0,1,0,3,2,3]
산출: 4

예시 3:

입력: 숫자 = [7,7,7,7,7,7,7]
산출: 1

제약:

1 <= 숫자.길이 <= 2500
-10 ⁴ <= 숫자[i] <= 10 ⁴

후속 조치: 실행되는 알고리즘을 생각해 낼 수 있습니까? O(n로그(n)) 시간복잡도?

파이썬

				
					# 시간 복잡도: O(n^2) # 공간 복잡도: O(1) import List 클래스 입력 시 솔루션: def lengthOfLIS(self, nums: List[int]) -> int: countList = [1] * len(nums ) for i in range(1, len(nums)): for j in range(i): if nums[i] > nums[j]: countList[i] = max(countList[i], countList[j] + 1) max(countList) nums = [0, 1, 0, 3, 2, 3] 반환 print(Solution().lengthOfLIS(nums))

중간

파이썬

관련 기사