Cod sursa(job #1893035)

Utilizator StefanaArinaStefana Arina Tabusca StefanaArina Data 25 februarie 2017 14:13:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100001
ifstream f("scmax.in");
ofstream g ("scmax.out");
int a[MAX], best[MAX], poz[MAX];
int n,m,first;


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

 void subsir()
 {
 int i,j;
 for(i=n;i>=1;i--)
{ best[i]=1;poz[i]=0;
 for(j=i+1;j<=n;j++)
    if(a[i]<a[j] && best[i]<1+best[j])
   {
     best[i]=1+best[j];
     poz[i]=j;
   }
 if(m<best[i])
    {
        m=best[i];
        first=i;
    }
 }
 }

 void tipar()
 {
 int i;
 g<<m<<endl;
 for(i=first;i>0;i=poz[i])
 g<<a[i]<<' ';
}
 int main()
 {
  citire();
  subsir();
  tipar();
  return 0;
 }