Cod sursa(job #999725)

Utilizator toncuvasileToncu Vasile toncuvasile Data 21 septembrie 2013 12:25:16
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
int n,A[100001],best[100001],l;
int main(){
   ifstream inFile("scmax.in");
   inFile>>n;
   for(int i=1;i<=n;i++) inFile>>A[i];

   ofstream outFile;
   outFile.open("scmax.out");

   best[1]=1;int maxB;
   for(int i=2;i<=n;i++){
     maxB=0;
     for(int j=1;j<=i-1;j++)
          if(A[i]>A[j] && best[j]>maxB) maxB=best[j];

     best[i]=maxB+1;
   }

   maxB=best[1];
   int index;
   for(int i=2;i<=n;i++) if(best[i]>maxB){ maxB=best[i];index=i;}
   outFile<<maxB<<"\n";
   int found[100001];
   found[maxB]=A[index];
   for(int i=index-1;i>=1;i--)
        if(best[i]+1==maxB){maxB--;found[maxB]=A[i];}

   for(int i=1;i<=best[index];i++) outFile<<found[i]<<" ";
}