Cod sursa(job #413091)

Utilizator eXtremeCornea Tudor eXtreme Data 7 martie 2010 17:28:54
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<iostream>
#include<fstream>
using namespace std;

int pred[100];
int best[100];
int v[100];
int n;
int imax=-1;

void read(ifstream & fin){
    fin>>n;
    for(int i=0;i<n;++i)
       fin>>v[i];
}    

void dinamic(){       
    best[n-1]=1;
    pred[n-1]=-1;
    for(int i=n-2;i>=0;--i){
        best[i]=1; pred[i]=-1;
        for(int j=i+1;j<n;++j)
          if(v[j]>v[i] && best[j]+1>best[i]){
              best[i]=best[j]+1;
              pred[i]=j;
              if(best[i]>best[imax]){
                  imax=i;
              }              
          }          
    }
}    

void sol(ofstream& out){
    int i=imax;
    while(i!=-1){
        out<<v[i]<<" ";
        i=pred[i];
    }    
      
}    

void print(int * v, int n){
    for(int i=0;i<n;++i)
        cout<<v[i]<<" ";
    cout<<endl;        
}    

int main(){
    ifstream in("scmax.in");
    ofstream out("scmax.out");
    read(in); 
    in.close();
    dinamic();
    
 //   print(v, n);
 //   print(best, n);
 //   print(pred, n);
    sol(out);
    out.close();
    
 system("pause");   
}