Cod sursa(job #2737437)

Utilizator alisavaAlin Sava alisava Data 4 aprilie 2021 19:08:18
Problema Subsir crescator maximal Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");
int a[100005], n;
int st[100005], top;
int dp[100005], answer[100005];
int BinarySearch(int val) /// actualizam primul element mai mare ca val
{
    int answer = 0;
    int s = 1;
    int f = top;
    while(s <= f)
    {
        int mid = (s + f) / 2;
        if(st[mid] >= val)
        {
            answer = mid;
            f = mid - 1;
        }
        else s = mid + 1;
    }
    st[answer] = val;
    return answer;

}




int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    for(int i = 1; i <= n; i++)
    {
        if(a[i] > st[top])
        {
            dp[i] = top + 1;
            st[++top] = a[i];
        }
        else
            dp[i] = BinarySearch(a[i]);
    }
    int cnt = top;
    for(int i = n; i >= 1; i--)
    {
        if(dp[i] == cnt)
        {
            answer[cnt] = a[i];
            cnt--;
        }
    }
    fout << top << "\n";
    for(int i = 1; i <= top; i++)
        fout << answer[i] << " ";

    return 0;
}