Cod sursa(job #1667261)

Utilizator CIOBBYXCiobanu Alin-Matei CIOBBYX Data 28 martie 2016 20:02:28
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include <iostream>
#include <fstream>
using namespace std;
int a[100005],ss[100005],urm[100005],i,j,sol=0,ras,pozmax,n;
int main()
{ ifstream f("scmax.in");
  ofstream g("scmax.out");
  f>>n;
  for (i=1;i<=n;i++)f>>a[i];
  ss[n]=1; urm[n]=-1;
  ras=1; pozmax=n;
  for (i=n-1;i>=1;i--) {
    ss[i]=1;
    urm[i]=-1;
    for (j=i;j<=n;j++)
    if (a[i]<a[j]&&ss[i]<ss[j]+1) {
        ss[i]=ss[j]+1;
        urm[i]=j;
        if(ss[i]>ras){ras=ss[i]; pozmax=i;}
    }
  }
  g<<ras<<"\n";
   i=pozmax;
   while (i!=-1) {
    g<<a[i]<<" ";
    i=urm[i];
   }
//   for (i=pozmax;i!=-1;i=urm[i]) g<<a[i]<<" ";
    return 0;
}