Mai intai trebuie sa te autentifici.
Cod sursa(job #2610950)
Utilizator | Data | 5 mai 2020 22:13:00 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.89 kb |
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
///Varianta o(n^2)
int n, a[nmax], lis[nmax], sol[nmax], nsol;
void Citire()
{
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
}
void Rezolvare()
{
int i, j, mx;
lis[1] = 1;
for (i = 2; i <= n; i++)
{
mx = 0;
for (j = i - 1; j >= 1; j--)
if (a[j] < a[i] && mx < lis[j])
mx = lis[j];
lis[i] = 1 + mx;
}
mx = 0;
for (i = 1; i <= n; i++)
mx = max(mx, lis[i]);
fout << mx << "\n";
for (i = n; i >= 1; i--)
if (lis[i] == mx)
{
sol[++nsol] = a[i];
mx--;
}
for (i = nsol; i >= 1; i--)
fout << sol[i] << " ";
}
int main()
{
Citire();
Rezolvare();
return 0;
}