Pagini recente » Cod sursa (job #2568508) | Cod sursa (job #1898933) | Cod sursa (job #3286144) | Cod sursa (job #2499918) | Cod sursa (job #2192570)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
int main() {
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n, elem, lmax = 1;
vector<int> val;
vector<int> dp;
stack<int> s;
fin >> n;
for(int i = 0; i < n; ++i) {
fin >> elem;
val.push_back(elem);
dp.push_back(1);
}
for (int i = 0; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (val[i] > val[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
if (dp[i] > lmax) {
lmax = dp[i];
}
}
fout << lmax << "\n";
int pos = n - 1;
while (dp[pos] != lmax) {
pos--;
}
s.push(val[pos]);
lmax--;
pos--;
for(; pos >=0 && lmax > 0; --pos) {
if (dp[pos] == lmax && val[pos] < s.top()) {
lmax--;
s.push(val[pos]);
}
}
while (!s.empty()) {
fout << s.top() << " ";
s.pop();
}
fin.close();
fout.close();
return 0;
}