Mai intai trebuie sa te autentifici.
Cod sursa(job #2261346)
Utilizator | Data | 16 octombrie 2018 10:24:54 | |
---|---|---|---|
Problema | Subsir crescator maximal | Scor | 70 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.87 kb |
#include <fstream>
#define NMAX 100010
std::ifstream fin("scmax.in");
std::ofstream fout("scmax.out");
int n;
int a[NMAX];
int lis[NMAX];
int prec[NMAX];
int main() {
int i, j;
int lisMax, posMax;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i];
lisMax = -1;
for (i = n; i >= 1; i--) {
lis[i] = 1;
prec[i] = 0;
for (j = i + 1; j <= n; j++)
if (a[i] < a[j] && lis[j] + 1 > lis[i]) {
lis[i] = lis[j] + 1;
prec[i] = j;
}
if (lis[i] > lisMax) {
lisMax = lis[i];
posMax = i;
}
}
fout << lisMax << '\n';
for (i = posMax; i <= n && lisMax; i++)
if (lis[i] == lisMax) {
lisMax--;
fout << a[i] << ' ';
}
fout.close();
return 0;
}