Pagini recente » Cod sursa (job #1777191) | Cod sursa (job #1625778) | Cod sursa (job #615560) | Cod sursa (job #1509044) | Cod sursa (job #1765872)
#include <iostream>
#include <fstream>
//Subsir strict crescator maximal
using namespace std;
const int MAXN = 100001;
ifstream f("scmax.in");
ofstream g("scmax.out");
int N, a[MAXN]; //Datele de intrare
int L[MAXN]; //L[i] = lungimea maxima a unui subsir crescator care incepe cu pozitia i
int lmax; //Lungimea maxima a unui subsir crescator
int poz; //Pozitia primului element din subsir
void dinamica()
{
L[N] = 1;
lmax = 1;
poz = N;
for(int i = N - 1; i >= 1; i--)
{
int maxs = 0;
for(int j = i + 1; j <= N; j++)
if(a[i] < a[j] && L[j] > maxs)
maxs = L[j];
L[i] = 1 + maxs;
if(L[i] > lmax)
{
lmax = L[i];
poz = i;
}
}
}
void subsir()
{
for(int i = poz; i <= N; i++)
if(a[i] >= a[poz] && L[i] == lmax)
{
g << a[i] << ' ';
lmax--;
}
}
int main()
{
f >> N;
for(int i = 1; i <= N; i++)
f >> a[i];
dinamica();
g << lmax << '\n';
subsir();
f.close();
g.close();
return 0;
}