Cod sursa(job #1144806)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 17 martie 2014 17:17:50
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
#define maxn 100005
using namespace std;
ifstream fi("scmax.in");
ofstream fo("scmax.out");

int a[maxn],lung[maxn],s[maxn],k;
int i,j,n,maxim;

int main(){
    fi>>n;
    for(i=1;i<=n;i++) fi>>a[i];
    
    //complexitate O(n^2)
    lung[1]=1;
    for(i=2;i<=n;i++){
                      maxim=1;
                      for(j=1;j<i;j++)
                         if(a[j]<a[i] && lung[j]+1>maxim) maxim=lung[j]+1;
                      
                      lung[i]=maxim;
                      if(maxim>k) k=maxim;
                     }
    
    maxim=k;
    for(i=n;i>0;i--)
      if(lung[i]==k) s[k--]=a[i];
    
    fo<<maxim<<"\n";
    for(i=1;i<=maxim;i++) fo<<s[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}