Pagini recente » Cod sursa (job #1077502) | Cod sursa (job #1046379) | Cod sursa (job #1081723) | Cod sursa (job #2548474) | Cod sursa (job #2419824)
#include <iostream>
#include <fstream>
#include <vector>
#define N_max 100000
int v[N_max];
int prec[N_max];
int N;
int last_poz;
void read_input()
{
std::ifstream f_in ("scmax.in");
f_in >> N;
for (int i = 0; i < N; i++) {
f_in >> v[i];
prec[i] = -1;
}
}
int compute_max_len()
{
std::vector<int> dp(N);
int max;
dp[0] = 1;
max = dp[0];
for (int i = 1; i < N; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (v[i] > v[j]) {
if (dp[j] + 1 > dp[i] && dp[j] + 1 > max) {
/* for max_len computation */
dp[i] = dp[j] + 1;
max = dp[i];
/* for reconstruction */
last_poz = i;
prec[i] = j;
}
}
}
}
return max;
}
void reconstruct(int max_len, std::ofstream &f_out)
{
int previous = 0, i = 0;
int succession[max_len];
succession[i++] = v[last_poz];
while (previous != -1) {
previous = prec[last_poz];
succession[i++] = v[previous];
last_poz = previous;
}
for (i = max_len - 1; i >= 0; i--)
f_out << succession[i] << " ";
f_out << std::endl;
}
void print_output(int max_len)
{
std::ofstream f_out ("scmax.out");
f_out << max_len << std::endl;
reconstruct(max_len, f_out);
}
int main() {
int max_len;
read_input();
max_len = compute_max_len();
print_output(max_len);
return 0;
}