Cod sursa(job #2497249)

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

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

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


int main(){
	fin >> n ;
	for(int i=1 ; i<=n ; ++i)
		fin >> a[i];
	L[n] = 1;
	nex[n] = -1;
	for(int i=n-1 ; i>0 ; i--)
	{
		L[i] = 1, nex[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, nex[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 = nex[i])
		fout << i << " ";
	return 0;
}