Cod sursa(job #177054)

Utilizator MciprianMMciprianM MciprianM Data 12 aprilie 2008 09:54:20
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
using namespace std;
#define M 100001
int n,  a[M], b[M], ant[M];
ofstream g("scmax.out");
void scrie(int i){
  if(i==0)  return;
  else {scrie(ant[i]);g<<a[i]<<' ';}
}
int main(){
  int i, j, max, imax;
  ifstream f("scmax.in");
  f>>n;
  for(i=1;i<=n;i++)
    f>>a[i];
  f.close();
  b[1]=1;
  for(i=2;i<=n;i++){
    int max=0;
    for(j=1;j<i;j++)
      if(a[j]<a[i] && b[j]>max){
	max=b[j];
	imax=j;
      }
    b[i]=max+1;
    ant[i]=imax;
  }
  max=0;
  for(i=1;i<=n;i++)
    if(max<b[i]){
      max=b[i];
      imax=i;
    }
  g<<max<<'\n';
  scrie(imax);
  g.close();
  return 0;
}