300. Longest Increasing Subsequence - medium
문제
Given an unsorted array of integers, find the length of longest increasing subsequence.
제한사항
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
- Could you improve it to O(n log n) time complexity?
입출력 예
1
2
3
4
5
Example 1:
Input: [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.
풀이
- DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty())
return 0;
vector<int> item(nums.size(), 1);
for(auto i = 1 ; i < nums.size() ; ++i){
// 현재 index 이전의 값을 조사
for(auto j = 0 ; j < i ; ++j){
// 현재 index값보다 작은 값일때,
// (현재 index의 값)과 (이전 index의 값 + 1)을 비교하여 큰값을 저장
// 가장긴 increasing subsequence이므로,
// 이전값에 현재 자기를 포함한 subsequence 이므로 +1 힘
if(nums[j] < nums[i]){
item[i] = max(item[i], item[j] + 1);
}
}
}
return *max_element(item.begin(), item.end());
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(auto i = 0; i < nums.size(); ++i) {
// low_bound를 통해 현재 index의 값과
// res의 값을 비교하여 위치할 곳을 찾음
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
// 현재 index의 값이 res내의 값들보다 크다면
// res에 현재 index의 값 추가
if(it == res.end())
res.push_back(nums[i]);
// 현재 index의 값이 res에 위치할 곳이 잇다면,
// 위치할곳의 값과 현재 index의 값과 바꿈
else
*it = nums[i];
}
// input이 [0, 4, 1, 5, 12, 2] 일때,
// 반복 횟수에 따른 res의 값들은 아래와 같음
// 0
// 0 4
// 0 1
// 0 1 5
// 0 1 5 12
// 0 1 2 12
return res.size();
}
};