Pagini recente » Cod sursa (job #1598657) | Cod sursa (job #2119029) | Cod sursa (job #219470) | Istoria paginii runda/daupentrumata | Cod sursa (job #2608757)
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
ifstream in("scmax.in");
ofstream out("scmax.out");
int main() {
int n, *v, *d;
in>>n;
v = new int[n + 1];
d = new int[n + 1];
for (int i = 1; i <= n; i++) {
in>>v[i];
}
d[1] = 1;
int maxLen = 0;
for (int i = 2; i <=n; i++) {
d[i] = 0;
for (int j = i - 1; j >= 1; j--) {
if (v[j] < v[i]) {
d[i] = max(d[i], d[j]);
}
}
d[i]++;
if (maxLen < d[i]) {
maxLen = d[i];
}
}
out<<maxLen<<"\n";
stack<int> s;
int tempLen = maxLen;
int lastEl;
int i;
for (i = n; i >= 1; i--) {
if (d[i] == tempLen) {
lastEl = v[i];
s.push(v[i]);
tempLen--;
break;
}
}
for (; i >= 1; i--) {
if (d[i] == tempLen && v[i] < lastEl) {
tempLen--;
lastEl = v[i];
s.push(v[i]);
}
}
while (!s.empty()) {
out<<s.top()<<" ";
s.pop();
}
return 0;
}