Cod sursa(job #2497245)

Utilizator D_ViorelDobrisor Viorel D_Viorel Data 22 noiembrie 2019 11:59:38
Problema Subsir crescator maximal Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
#define NN 100005

ifstream fin("scmax.in");
ofstream fout("scmax.out");

int n, a[NN], L[NN], next[NN];


int main(){
	assert(fin >> n );
	for(int i=1 ; i<=n ; ++i)
		assert(fin >> a[i]);
	L[n] = 1;
	next[n] = -1;
	for(int i=n-1 ; i>0 ; i--)
	{
		L[i] = 1, next[i] = -1;
		for(int j=i+1 ; j<=n; ++j)
			if(a[i]<=a[j] && L[i]<L[j]+1)
				L[i] = L[j] + 1, next[i] = j;
	}
	int pmax = 1;
	for(int i=1 ; i<=n ; ++i)
		if(L[pmax] < L[i])
			pmax = i;
	fout << L[pmax] << endl;
	for(int i=pmax ; i!=-1 ; i = next[i])
		fout << i << " ";
	return 0;
}