Pagini recente » Cod sursa (job #1976498) | Cod sursa (job #477979) | Cod sursa (job #1139963) | Profil livache2001 | Cod sursa (job #2743896)
#include <iostream>
using namespace std;
int main() {
ifstream("scmax.in");
ofstream("scmax.out");
uint64_t N;
fin >> N;
N++;
int64_t *v = (int64_t *)malloc(sizeof(int64_t) * N);
uint64_t i, j;
for (i = 1; i < N; i++) {
fin >> v[i];
}
int64_t *dp = (int64_t *)malloc(sizeof(int64_t) * N);
int64_t *prec = (int64_t *)malloc(sizeof(int64_t) * N);
dp[1] = 1;
prec[1] = 1;
for (i = 2; i < N; i++) {
int64_t index_dp = -1;
for (j = 1; j < i; j++) {
if (v[i] > v[j]) {
if ((index_dp != -1 && dp[j] > dp[index_dp]) || index_dp == -1) {
index_dp = j;
}
}
if (index_dp != -1) {
dp[i] = 1 + dp[index_dp];
prec[i] = index_dp;
} else {
dp[i] = 1;
prec[i] = 1;
}
}
}
int64_t sol = dp[1];
int64_t index_sol = 1;
for (i = 2; i < N; i++) {
if (dp[i] > sol) {
sol = dp[i];
index_sol = i;
}
}
fout << sol << '\n';
int64_t *best_subseq = (int64_t *)malloc(sizeof(int64_t) * sol);
int64_t cnt = 0;
while (index_sol != prec[index_sol]) {
best_subseq[cnt++] = v[index_sol];
index_sol = prec[index_sol];
}
int64_t k;
for (k = sol - 1; k > -1; k--) {
fout << best_subseq[k] << ' ';
}
fout << '\n';
}