Cod sursa(job #1502408)

Utilizator Daniel_UngureanuUngureanu Daniel Daniel_Ungureanu Data 14 octombrie 2015 17:06:15
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>

using namespace std;
int best[100001],poz[100001],v[100001];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main()
{
    int n,j,i,max=0,p;
    f>>n;
    for(i=1;i<=n;i++)
        f>>v[i];
    best[n]=1;
    poz[n]=-1;
    for(i=n-1;i>=1;i--)
    {
        best[i]=1;
        poz[i]=-1;
        for(j=i+1;j<=n;j++)
            if(v[i]<v[j]&&best[i]<best[j]+1)
            {
                best[i]=best[j]+1;
                poz[i]=j;
            }
        if(best[i]>max)
        {
            max=best[i];
            p=i;
        }

    }
    g<<max<<"\n";
    while(p!=-1)
    {
        g<<v[p]<<" ";
        p=poz[p];
    }


    return 0;
}