안녕하세요~ 동적계획법 4번 LIS 문제 질문 있습니다.

안녕하세요^^

LIS 문제를 O(NlogN) 복잡도로 짜는 방법이 있습니다. 이분검색을 이용하는 방법인데 다음 코드가 바로 그 방법입니다.

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	freopen("input.txt", "rt", stdin);
    int n, a;
    cin>>n;
    vector<int> arr;
    arr.push_back(-2147000000);
    for(int i=0; i<n; i++) {
        cin>>a;
        if(a>arr.back()) arr.push_back(a);
        else{
            auto it=lower_bound(arr.begin(), arr.end(), a);
            *it=a;
        }
        //for(auto x : arr) cout<<x<<" ";
        //cout<<endl;
    }
    cout<<arr.size()-1;
    return 0;
}

위에 코드에서 lower_bound 함수가 이분검색으로 a이상의 값 중 가장 작은 수의 위치를 찾아 줍니다. lower_bound에 대해서구글링해보세요.

너무 감사합니다~ .아직 공부할것이 많은것 같습니다.  열심히 해보겠습니다. 

감사합니다. 건강 조심하세요~