Cod sursa(job #1599796)

Utilizator RaTonAndrei Raton RaTon Data 14 februarie 2016 13:37:16
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int v[100000];
int d[100000];
int main(){
	int n, i, j, poz, max;
	f >> n;
	for( i = 0; i < n; i++ )
		f >> v[i];
	d[n-1] = 1;
	poz = n - 1;
	max = 1;
	for( i = n - 2; i >= 0; i-- )
		if( v[i] < v[i+1] ){
			d[i] = d[i+1] + 1;
			if( d[i] > max ){
				max = d[i];
				poz = i;
			}
		}
		else{
			j = i + 2;
			while( v[i] >= v[j] && j < n )
				j++;
			if( j < n ){
				d[i] = d[j] + 1;
				if( d[i] > max ){
					max = d[i];
					poz = i;
				}
			}
			else
				d[i] = 1;
		}
	g << max << "\n";
	g << v[poz] << " ";
	max--;
	i = poz + 1;
	while( max > 0 ){
		if( v[i] > v[poz] ){
			g << v[i] << " ";
			poz = i;
			max --;
		}
		i++;
	}		
	return 0;
}