Cod sursa(job #1765333)

Utilizator LizaSzabo Liza Liza Data 26 septembrie 2016 17:30:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>

using namespace std;
ifstream f1("scmax.in");
ofstream f2("scmax.out");

 int i,j,n,x[100005],DP[100005],sol,k,l,maxx;
void cit(){
f1>>n;
for(i=1;i<=n;i++){

    f1>>x[i];
}
}


void rez(){
for (i=n;i>=1;i--){
    for(j=i+1;j<=n;j++){
        if(x[i]<x[j]&&DP[j]>DP[i]){
            DP[i]=DP[j];
        }
    }
        DP[i]++;

}
sol=1;
for(i=1;i<=n;i++)
{
    if (DP[i]>sol)
        {l=i;};
    sol=max(sol,DP[i]);
}

f2<<sol<<'\n';

k=1; maxx=x[l];
f2<<x[l]<<' ';
int Nr = sol-1;
while(k<sol)
{
    l++;
    if(x[l]>maxx && DP[l] == Nr)
        {f2<<x[l]<<' ';  k++; maxx=x[l]; Nr--;}}
}

int main()
{
    cit();
rez();
    return 0;
}