Cod sursa(job #1075747)

Utilizator chimistuFMI Stirb Andrei chimistu Data 9 ianuarie 2014 15:30:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#define MAXN 100001

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int n,sir[MAXN],best[MAXN],maxim,poz[MAXN],last;

void dinamica(){
    int i,j;
    best[n]=1;
    poz[n]=-1;
    maxim=1;
    last=n;
    for(i=n-1;i>=1;i--){
        best[i]=1;
        poz[i]=-1;
        for(j=i+1;j<=n;j++)
            if(sir[i]<sir[j] && best[i]<best[j]+1){
                best[i]=best[j]+1;
                poz[i]=j;
                if(best[i]>maxim){
                    maxim = best[i];
                    last=i;
                }
            }
    }
}


int main()
{
    int i;
    f >> n;
    for(i=1;i<=n;i++){
        f >> sir[i];
    }
    dinamica();
    g << maxim << "\n";
    i=last;
    while (i!=-1){
        g << sir[i] << " ";
        i=poz[i];
    }


    return 0;
}