Cod sursa(job #1332678)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 2 februarie 2015 12:06:58
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <iostream>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;
int n,x[100001],c[100001],i,j,MAX;
int drum[100001],poz;
ifstream f("scmax.in");
ofstream g("scmax.out");
int main()
{
    f>>n;
    for(i=0;i<n;i++)
        f>>x[i];
    c[n-1]=1;

    for(i=n-1;i>=0;i--){
        c[i]=1;
        for(j=i+1;j<n;j++)
            if(x[i]<x[j]){
                if(1+c[j]>c[i]){
                    c[i]=1+c[j];
                    drum[i]=j;
                }
            }
    }
    MAX=c[0];
    for(i=0;i<n;i++)
        if(MAX<c[i]){
            MAX=c[i];
            poz=i;
        }
    g<<MAX<<'\n';
    for(i=1;i<=MAX;i++){
        g<<x[poz]<<' ';
        poz=drum[poz];
    }
    return 0;
}