Cod sursa(job #1103906)

Utilizator Aavatar36Russu Vadim Aavatar36 Data 10 februarie 2014 08:52:59
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
using namespace std;
int a[100000], l[100000], urm[100000], sum[100000];
int n, mx, mxs, mxp;

int ur(int p) {
	int i;
	for (i = p + 1; i < n; i++) {
		if (a[i] > a[p]) {
			urm[p] = i;
			break;
		}
	}
	return 0;
}

int lun(int p) {
	int i;
	if (urm[p] == 0) {
		l[p] = 1;
		return 0;
	}
	l[p] = 1 + l[urm[p]];
	if (l[p] > mx) {
		mx = l[p];
	}
	return 0;
}

int sm(int p) {
	int i;
	sum[p] = a[p] + sum[urm[p]];
	if (sum[p] > mxs) {
		mxs = sum[p];
		mxp = p;
	}
	return 0;
}




int main() {
	ifstream fin("scmax.in");
	ofstream fout("scmax.out");
	fin >> n;
	int i;

	for (i = 0; i < n; i++) {
		fin >> a[i];
	}
	for (i = 0; i < n; i++) {
		ur(i);
	}
	sum[n - 1] = a[n - 1];
	for (i = n - 1; i >= 0; i--) {
		lun(i);
		sm(i);
	}
	i=mxp;
	fout << l[mxp]<<endl;
	while(1){
	 fout << a[i] << " ";
	 i=urm[i];
	 if (i==0) {
	   break;
	 }
	}
   //	fout << endl << mxs;
	return 0;
}