Cod sursa(job #1155375)

Utilizator tudi98Cozma Tudor tudi98 Data 26 martie 2014 21:08:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#define dim 100001
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");

int Y,a[dim],poz[dim],best[dim],BEST=-100000,i,j,n,c=1;

int main(){

    f>>n;
    for(i=1;i<=n;i++)
    f>>a[i];

    best[n]=1,poz[n]=n;
    for(i=n-1;i>=1;i--){

        for(j=n;j>i;j--){
            if(a[j]>a[i] && best[i]<best[j]+1){
                 poz[i]=j;
                 best[i]=best[j]+1;
            }
            if(!best[i]) best[i]=1,poz[i]=i;
        //    g<<best[i]<<" ";
            if(best[i]>BEST) BEST=best[i],Y=i;
        }
    }
        g<<BEST<<"\n";
        while(poz[Y]!=Y){
            g<<a[Y]<<" ";
            Y=poz[Y];
        }
            g<<a[Y];
}