Cod sursa(job #669357)

Utilizator harababurelPuscas Sergiu harababurel Data 26 ianuarie 2012 20:10:11
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
using namespace std;
int cost[100001];
int main() {
	ifstream f("scmax.in");
	ofstream g("scmax.out");
	int n, a[100001], i, j, max=1, lungmax=0, pozmax=0;
	f>>n;
	for(i=1; i<=n; i++) f>>a[i];
	
	cost[n]=1;
	for(i=n-1; i>=1; i--) {
		max=0; cost[i]=1;
		for(j=i+1; j<=n; j++) {
			if(a[i]<a[j] && cost[j]>max) { max=cost[j]; }
		}
		
		cost[i]=max+1;
		if(cost[i]>lungmax) { lungmax=cost[i]; pozmax=i; }
		
		
	}
	
	g<<lungmax<<"\n";
	
	max=cost[pozmax]; 
	g<<a[pozmax]<<" ";
	
	for(i=pozmax+1; i<=n; i++) {
		if(a[i]>a[pozmax] && cost[i]==max-1) { max--; g<<a[i]<<" "; }
	}
	
	
	
		
		
	
	
	
//	for(i=1; i<=n; i++) g<<cost[i]<<" ";
	
	f.close();
	g.close();
	return 0;
}