Cod sursa(job #1619274)
| Utilizator | Data | 28 februarie 2016 14:39:54 | |
|---|---|---|---|
| Problema | Subsir crescator maximal | Scor | 70 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
#include <cstring>
using namespace std;
int n, i, j, a[100001], lu[100001],pa[100001], inc, ma;
ifstream f ("scmax.in");
ofstream g ("scmax.out");
int main () {
f>>n;
for (i=1; i<=n; i++) {
f>>a[i];
}
for (i=1; i<=n; i++) {
lu[i]=1;
}
pa[n]=0;
for (i=n-1; i>=1; i--) {
for (j=n; j>i; j--) {
if (a[i]<a[j]&&lu[j]+1>=lu[i]) {
lu[i]=lu[j]+1;
if (lu[j]+1>=ma) {ma=lu[j]+1; inc=i;}
pa[i]=j;
}
}
}
g<<ma<<'\n';
for (i=1; i<=ma; i++) {
g<<a[inc]<<" ";
inc=pa[inc];
}
return 0;
}
