Cod sursa(job #802344)

Utilizator alextudose95Tudose Stefan Alexandru alextudose95 Data 26 octombrie 2012 15:27:11
Problema Subsir crescator maximal Scor 0
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 main()
{
   long int v[10000],l[10000],tata[10000],i,n,max,pm,j,mx;
   f>>n;
   for (i=1;i<=n;i++) f>>v[i];
   l[n]=1;tata[n]=0;
   for (i=n-1;i>0;i--)
   {
       max=0;
       for (j=i+1;j<=n;j++) if ((v[i]<v[j])&&(l[j]>max))
       {
           max=l[j];
           pm=j;
       }
      if (max==0) {tata[i]=0;l[i]=1;}
      else { l[i]=max+1;tata[i]=pm; }
   }
   mx=0;
   for (i=1;i<=n;i++) if (mx<l[i]) {mx=l[i];j=i;}
   g<<"Lungimea SCM = "<<mx<<endl;
   i=j;g<<v[i]<<" ";
   while (tata[i]!=0) {g<<v[tata[i]]<<" ";i=tata[i];}
   f.close();
   g.close();
}