Cod sursa(job #979072)

Utilizator catalincraciunCraciun Catalin catalincraciun Data 31 iulie 2013 14:55:05
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
/// Craciun Catalin
///  Sir crescator de lungime maxima
///   www.infoarena.ro/problema/scmax
///    Programare dinamica
#include <fstream>
#include <iostream>

using namespace std;

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

int main(){

    long n;
    long long A[100001];
    long L[100001]; /// Lungimea sirului crescator incepand cu pozitia i
    long Poz[100001]; /// Urmatorul element din sirul crescator

    /// Citire
    f>>n;
    for (long i=1;i<=n;i++)
        f>>A[i];
    f.close();

    L[n]=1;
    Poz[n]=-1;

    for (long i=n-1;i>=1;i--){
        L[i]=1;
        Poz[i]=-1;
        for (long j=i+1;j<=n;j++){
            if (A[i]<=A[j] && L[i]<1+L[j]){
                L[i]=1+L[j];
                Poz[i]=j;
            }
        }
    }

    long max=L[1];
    long pozMax=1;
    for (long i=2;i<=n;i++)
        if (max<L[i]){
            max=L[i];
            pozMax=i;
        }

    /// Afisare
    g<<max<<"\n";
    for (long i=pozMax;i!=-1;i=Poz[i])
        g<<A[i]<<" ";
    g.close();

    return 0;
}