[LeetCode] 300. Longest Increasing Subsequence

문제 URL :https://leetcode.com/problems/longest-increasing-subsequence/

Longest Increasing Subsequence - LeetCode

문제 접근법 : 정말오랜만에 보는 LIS 알고리즘 문제입니다.

이중 for문을 이용해서 풀어도됩니다.

그러나 이것은 백준문제에도 예전에 풀어놓았던게 있었던거라 따로 설명은 드리지않고

바로 코드를 드리겠습니다.

 

소스코드 : 

 

class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
	vector<int> res={-1000000};
	for(int t:nums){
		if(res.back()<t){
			res.push_back(t);
		}
		else{
			*lower_bound(res.begin(),res.end(),t)=t;
		}
	}
	return res.size()-1;        
}
};

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.