Cod sursa(job #1992522)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 20 iunie 2017 17:17:12
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
#define MAX 100001

using namespace std;

int n,r,s[MAX],a[MAX],smax,imax,sr[MAX],l,nra;

int main()
{
    ifstream f ("scmax.in");
    ofstream g ("scmax.out");
    f>>n;
    for(int i=1;i<=n;i++){
      f>>a[i];
      r=0;
      for(int j=i-1;j>=1;j--)
        if(s[j]>r&&a[j]<a[i])r=s[j];
      s[i]=r+1;
      if(s[i]>smax){
        smax=s[i];
        imax=i;
      }
    }
    g<<smax<<'\n';
    sr[++l]=a[imax]; nra=imax;
    for(int i=imax-1;i>=1;i--){
      if(a[i]<a[nra]&&s[i]==s[nra]-1){
        sr[++l]=a[i];
        nra=i;
      }
    }
    for(int i=l;i>=1;i--)g<<sr[i]<<" ";
    f.close ();
    g.close ();
    return 0;
}