Cod sursa(job #1726637)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 8 iulie 2016 15:59:10
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#define NMAX 100005
using namespace std;

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

int a[NMAX], n, dp[NMAX], maxim=1, imax=n-1;
void citire()
{
    in>>n;
    for(int i=0; i<n; i++)
        in>>a[i];
}

int maxi(int p)
{
    int s=0;
    for(int i=p+1; i<n; ++i)
        if(dp[i]>s && a[i]>a[p]) s=dp[i];
    return s;
}
void lung_max()
{
    dp[n-1]=1;
    for(int i=n-2; i>=0; i--)
        {
            dp[i]=1+maxi(i);
            if(dp[i]>maxim)
               {
                   maxim=dp[i];
                   imax=i;
               }
        }
}
void afisare()
{
    for(int i=imax; i<n; i++)
        if(dp[i]>dp[i+1]) out<<a[i]<<" ";
}
int main()
{
    citire();
    lung_max();
    out<<maxim<<"\n";
    afisare();
    return 0;
}