Cod sursa(job #979660)

Utilizator TibixbAndrei Tiberiu Tibixb Data 2 august 2013 12:15:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#define DIM 2000000010
using namespace std;
int i, n, d[100002], v[100002], maxim, pmaxim, j, t[100002], sol[100002], k;
FILE*fin=fopen("scmax.in","r");
ofstream fout("scmax.out");
int main() {
     fscanf(fin, "%d", &n);
     for(i=1; i<=n; i++)
        fscanf(fin, "%d", &v[i]);
    d[1]=1;
    v[++n]=DIM;
    for(i=2; i<=n; i++){
        maxim=0;
        pmaxim=0;
        for(j=1; j<i; j++){
            if(v[j]<v[i] && d[j]>maxim){
                maxim=d[j];
                pmaxim=j;
            }
        }
        d[i]=1+maxim;
        t[i]=pmaxim;
    }
    i=n;
    while(i!=0){
        sol[++k]=v[i];
        i=t[i];
    }
    fout<<d[n]-1<<"\n";
    for(i=k; i>=2; i--)
        fout<<sol[i]<<" ";
    return 0;
}