Pagini recente » Cod sursa (job #1234594) | Cod sursa (job #32924) | Cod sursa (job #2233752) | Cod sursa (job #1091484) | Cod sursa (job #1430921)
#include <iostream>
#include <fstream>
#include <vector>
void maxSeq (std::vector<int> &v, int n) {
std::vector<int> maxim (n, 1);
std::vector<int> next (n, - 1);
std::vector<int> maxSubsequence;
// maxim[n-1] = 1;
// next[n-1] = -1;
for (int i = n - 2; i >= 0; --i) {
// maxim[i] = 1;
// next[i] = -1;
for (int j = i + 1; j < n; ++j) {
if (v[i] < v[j] && maxim[i] <= maxim[j]) {
maxim[i] = maxim[j] + 1;
next[i] = j;
}
}
}
int len = maxim[0];
int startFrom = 0;
for (int i = 1; i < n; ++i) {
if (len < maxim[i]) {
len = maxim[i];
startFrom = i;
}
}
maxSubsequence.push_back (v[startFrom]);
for (int i = 1; i < n; ++i) {
startFrom = next[startFrom];
maxSubsequence.push_back (v[startFrom]);
}
std::ofstream g ("scmax.out");
g << len << "\n";
for (int i = 0; i < len; ++i) {
g << maxSubsequence[i] << " ";
}
g << "\n";
g.close();
maxim.clear();
next.clear();
maxSubsequence.clear();
}
int main (void) {
std::ifstream f ("scmax.in");
int n;
f >> n;
std::vector<int> v (n, 0);
for (int i = 0; i < n; ++i) {
f >> v[i];
}
maxSeq (v, n);
v.clear();
f.close();
return 0;
}