Cod sursa(job #1330683)

Utilizator rsteliRadu Stelian rsteli Data 30 ianuarie 2015 21:22:47
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
using namespace std;
ifstream cin("scmax.in");
ofstream cout("scmax.out");

#define nmax 100010

int n,maxim1,ind1,maxim2,ind2;
int v[nmax],p[nmax],t[nmax];

int main()
{
    int i,j;
    cin>>n;
    cin>>v[1];
    for (i=2;i<=n;i++)
    {
        cin>>v[i];
        maxim1=0;
        for (j=i-1;j;j--)
            if (v[i]>v[j])
            {
                if (p[j]>maxim1)
                {
                    maxim1=p[j];
                    ind1=j;
                }
                p[i]=maxim1+1;
                if (p[i]>maxim2)
                {
                    maxim2=p[i];
                    ind2=i;
                }
            }
    }
    j=ind2;
    for (i=ind2;i;i--)
        if (p[i]==p[j]-1)
        {
            t[++t[0]]=i;
            j=i;
        }
    cout<<t[0]+1<<'\n';
    for (i=t[0];i;i--)
        cout<<v[t[i]]<<" ";
    cout<<v[ind2];
}