Pagini recente » Cod sursa (job #2113122) | Cod sursa (job #2631938) | Cod sursa (job #1771643) | Cod sursa (job #897533) | Cod sursa (job #2280413)
#include <iostream>
#include <fstream>
typedef long long T;
const int NMAX = 100005;
int N;
T arr[NMAX];
T best[NMAX];
T pre[NMAX];
/*
*
* am asa
* best_i = 1 + max(best_j)
* pre_i -> pozitie valorii care preceda elementul i din subsir
*
*/
int main() {
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
scanf("%d", &N);
for (int i = 0; i < N; ++i) {
scanf("%lld", &arr[i]);
}
T max = -1;
int p = -1;
for (int i = 0; i <= N; ++i ) {
best[i] = 1;
pre[i] = -1;
}
best[N-1] = 1;
pre[N-1] = -1;
for (int i = N-1; i >= 0; --i) {
best[i] = 1;
pre[i] = -1;
for (int j = i+1; j < N; ++j) {
if (arr[i] < arr[j] && best[i] < best[j] + 1) {
best[i] = best[j] + 1;
pre[i] = j;
if (max < best[i]) {
max = best[i];
p = i;
}
}
}
}
printf("%lld\n", max);
while (p != -1) {
printf("%lld ", arr[p]);
p = pre[p];
}
return 0;
}