12015번: 가장 긴 증가하는 부분 수열 2

https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

A의 i - 1번째 성분까지의 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. A의 i번째 성분 Ai가 lis의 맨 마지막 성분보다 크다면 lis의 맨 뒤에 Ai를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 Ai보다 작은 값 중 가장 큰 값을 Ai로 대체해 Ai 이후의 값을 갱신할 수 있게 한다. 이 때 lis의 값을 Ai로 대체하는 경우 Ai보다 전에 나온 값이 Ai 이후에 위치하므로 부분 수열의 규칙을 무시하지만, 길이 자체는 변하지 않는다.

#include <algorithm>
#include <iostream>

using namespace std;

#define MAX_N 1000000

int main() {
    // 입출력 속도 향상
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    // N: 수열의 길이, A: 각 수열의 성분
    // lis: 가장 긴 증가하는 부분 수열, len: lis의 길이
    int N, A, lis[MAX_N] = { 0, }, len = 0;

    // 각 수열의 성분에 대해
    for (cin >> N; N--; ) {
        // 각 수열의 성분을 입력받고
        cin >> A;
        // 증가하는 부분 수열 lis이 비었거나 A가 lis의 마지막 값보다 크다면
        // lis의 맨 뒤에 A를 추가
        if (!len || lis[len - 1] < A) lis[len++] = A;
        // 그렇지 않다면 lis에서 A보다 작은 값 중 가장 큰 값을 A로 변경
        // 부분 수열의 순서에는 영향을 미치지만 부분 수열의 길이에는 영향을 주지 않음
        else *lower_bound(lis, lis + len, A) = A;
    }

    // 가장 긴 증가하는 부분 수열의 길이를 출력
    cout << len << '\n';

    return 0;
}