Cod sursa(job #951316)

Utilizator Darius15Darius Pop Darius15 Data 20 mai 2013 09:39:48
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include <fstream>

using namespace std;
#define nmax 100002
int n,i,a[nmax],best[nmax],j,maxi,maxim,poz,k;
ifstream f("scmax.in");
ofstream g("scmax.out");
void c()
{
    f>>n;
    for (i=1;i<=n;i++)
        f>>a[i];
}
void dinamica()
{
    best[n]=1;
    maxim=0;
    for (i=n-1;i>=1;i--){
            maxi=0;
    for (j=i+1;j<=n;j++)
    if (a[i]<a[j] && maxi<best[j]) maxi=best[j];
    best[i]=maxi+1;
    if (best[i]>maxim) maxim=best[i],poz=i;
    }
}
void reconst()
{
   for (k=poz;k<=n;k++)
    if (a[poz]<=a[k] && best[k]==maxim) g<<a[k]<<' ',maxim--,poz=k;
}
int main()
{
    c();
    dinamica();
    g<<maxim<<'\n';
    reconst();
    return 0;
}