Cod sursa(job #485345)

Utilizator PopaStefanPopa Stefan PopaStefan Data 18 septembrie 2010 10:13:39
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include<fstream>
#define nmax 100001
#define infinit 2000000

using namespace std;

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n,a[nmax],l[nmax],pre[nmax];

void citire()
{fin>>n;
for(int i=1;i<=n;i++)
  fin>>a[i];
}

void solve()
{l[n]=1;
int i,j,maxx,poz,inceput=-infinit,pozz;
pre[n]=-1;
for(j=n-1;j>=1;j--)
  {maxx=-infinit;
   for(i=j+1;i<=n;i++)
      if(l[i]>maxx && a[i]>a[j])
        {maxx=l[i];
         poz=i;
        }
  if(maxx!=-infinit)
       {l[j]=1+maxx;
        pre[j]=poz;
       }
    else {l[j]=1;
          pre[j]=-1;
         }
  if(l[j]>inceput)
     {inceput=l[j];
      pozz=j;
     }
  }
fout<<l[pozz]<<'\n';
i=pozz;
while(i<=n && i!=-1)
  {fout<<a[i]<<" ";
   i=pre[i];
  }
}

int main()
{citire();
solve();
return 0;
}