# PBinfo #396 – SCLM – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

Cerinţa
Se dă un șir cu n elemente, numere naturale. Determinați un cel mai lung subșir crescător (nu neapărat strict) al șirului.

Date de intrare
Fişierul de intrare sclm.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând elementele șirului.

Date de ieşire
Fişierul de ieşire sclm.out va conţine pe prima linie numărul L, reprezentând lungimea maximă a unui subșir crescător. A doua linie va conține L numere cu valori între 1 și n, ordonate crescător, reprezentând indicii elementelor din șirul dat care dau subșirul crescător de lungime maximă.

Restricţii şi precizări

1 ≤ n ≤ 1000
numerele de pe a doua linie a fişierului de intrare vor fi cel mult egali cu 1.000.000
orice șir de indici care duce la subșir crescător de lungime maximă este corect

Exemplu:
sclm.in

10
5 10 7 4 5 8 9 8 10 2 
sclm.out

5
1 3 6 7 9 
Explicație
Elementele șirului care corespund acestor indici sunt: 5 7 8 9 10.

## Cod sursă C++

```cpp
#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], 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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/396)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/396/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-396/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)