문제 내용
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4
Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1
Constraints:
1 <= nums.length <= 2500
-104 <= nums[i] <= 104
문제 접근
해당 방법은 완전탐색으로는 N^3이 걸린다. 때문에 연산의 제약조건으로 탈락
그러면 dp 나 그리디로 풀어야 된다.
1시간 동안 고민해보고 dp에 대한 실마리를 잡았지만 해결하지 못했다.
dp
잘 생각해보면 우리는 마지막 부분만을 정해주면 어디까지 최대 길이인지 알 수 있다.
구체적으로 1, 2, 4, 5, 2, 3 을 살펴보자.
1은 처음이므로 길이가 1이다.
2는 1보다 크므로 길이가 2이다.
여기서 4가 등장했을 때 dp로 어떻게 해결해야 할까?
우리는 2까지 최대길이를 안다. 때문에 해당 인수들이 4보다 작은지 확인하고, 자기 자신을 더한 것과 비교하면서 갱신해 나가면 된다.
코드로 직접보면 이해하기 수월하다.
dp 구현
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], 1 + dp[j])
return max(dp)
patience sort 알고리즘
이미 해당 문제에 대해 석박사 님들이 최적 알고리즘을 구현해놓았다.
이진탐색을 활용해 그때그때 최적의 부분 최대 길이를 구하는 알고리즘이다.
nlogn으로 시간복잡도가 확 줄었다.
https://en.wikipedia.org/wiki/Patience_sorting
https://wordaligned.org/articles/patience-sort
greedy 및 이진탐색으로 위의 알고리즘 구현
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for num in nums:
i = bisect.bisect_left(dp, num)
if i == len(dp):
dp.append(num)
else:
dp[i] = num
return len(dp) 
