Cod sursa(job #2164900)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 13 martie 2018 10:21:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<bits/stdc++.h>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int N,v[100001],best[100001],poz[100001],Max,idx;
int main()
{
    f>>N;
    for(int i=1;i<=N;++i)f>>v[i],best[i]=1,poz[i]=-1;
    for(int i=2;i<=N;++i){
        for(int j=1;j<i;++j)
            if(v[j]<v[i]&&best[j]+1>best[i]){
                    best[i]=best[j]+1,poz[i]=j;
            }
        if(best[i]>Max)Max=best[i],idx=i;
    }
    g<<Max<<'\n';
    int k=idx;
    idx=Max;
    while(k!=-1)best[idx--]=v[k],k=poz[k];
    for(int i=1;i<=Max;++i)g<<best[i]<<' ';
    return 0;
}