Mai intai trebuie sa te autentifici.
Cod sursa(job #1864395)
| Utilizator | Data | 31 ianuarie 2017 18:56:28 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.95 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
const int maxn = 1e5 + 5;
int V[maxn], Best[maxn], Pre[maxn];
int main() {
ios_base :: sync_with_stdio (false);
int n, i, j, maxx, p;
fin >> n;
for (i = 1; i <= n; i++) {
fin >> V[i];
}
Best[n] = 1;
Pre[n] = -1;
maxx = 1;
p = n;
for (i = n - 1; i; i--) {
Best[i] = 1;
Pre[i] = -1;
for (j = i + 1; j <= n; j++) {
if (Best[j] + 1 > Best[i] && V[j] > V[i]) {
Best[i] = Best[j] + 1;
Pre[i] = j;
}
if (Best[i] > maxx) {
maxx = Best[i];
p = i;
}
}
}
fout << maxx << "\n";
i = p;
while (i != -1) {
fout << V[i] << " ";
i = Pre[i];
}
fin.close();
fout.close();
return 0;
}
