Cod sursa(job #1871782)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 7 februarie 2017 17:33:02
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,i,j;
int v[NMAX],c[NMAX],MAX=0,sol[NMAX],poz;
int main(){
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    c[n]=1;
    for(i=n;i>=2;i--){
        for(j=i;j<=n;j++)
            if(v[i-1]<v[j]&&c[i-1]<c[j]+1){
                c[i-1]=c[j]+1;
                sol[i-1]=j;
            }
    }
    MAX=0;
    for(i=1;i<=n;i++){
        if(MAX<c[i]){
            MAX=c[i];
            poz=i;
        }
    }
    g<<MAX<<'\n';
    for(i=1;i<=MAX;i++){
        g<<v[poz]<<' ';
        poz=sol[poz];
    }
    return 0;
}