12738 가장 긴 증가하는 부분 수열 3

 

생각주간에 가장 긴 증가하는 부분수열 문제 있는 거 보고 이번에는 NlogN으로 푸는 거 공부해서 적용해야겠다!! 싶었는데 합이 가장 큰 걸 구하라고 해서 다른 문제로 제출했다. 이 알고리즘 세 번 봤는데 세 번 다 이해 못해서 낑낑거리다가 드디어 이해했다. 이제는 좀 알겠음. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int     main()
{
    int n;
    scanf("%d", &n);

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);


    vector<int> dp;
    dp.push_back(v[0]);
    for (int i = 1; i < n; i++)
    {
        if (dp[dp.size()-1] < v[i])
        {
            dp.push_back(v[i]);
            continue;
        }
        int pos = lower_bound(all(dp), v[i]) - dp.begin();
        dp[pos] = v[i];
    }
    printf("%d\n", dp.size());
    return 0;
}

 

 

 

 

mygumi.tistory.com/303

LIS 최장증가수열 알고리즘 -2- :: 마이구미

 

yabmoons.tistory.com/560