Cod sursa(job #1649588)

Utilizator GeanaVladGeana Vlad GeanaVlad Data 11 martie 2016 14:17:34
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <iostream>
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100001],d[100001],n,i,j,mx,pmax,a[100001];
int main()
{
   f>>n;
   for(i=1;i<=n;i++) f>>v[i];
   for(i=1;i<=n;i++) d[i]=1;
   for(i=2;i<=n;i++)
   for(j=1;j<i;j++)
   {
       if(v[j]<v[i])
        {
            d[i]=max(d[i],d[j]+1);
            if(d[i]>mx) {pmax=i;mx=d[i];}
        }
   }
   g<<mx<<endl;
   a[mx]=v[pmax];
   int mx1=mx;
   int p=pmax;
   while(d[p]!=1)
   {
       for(i=p-1;i>=1;i--)
           if(d[i]==d[p]-1 && v[i]<v[p])
           break;
       p=i;
       mx1--;
       a[mx1]=v[i];
   }
   for(j=1;j<=mx;j++) g<<a[j]<<' ';
}