Pagini recente » Cod sursa (job #571303) | Cod sursa (job #945451) | Cod sursa (job #1371198) | Cod sursa (job #2675700) | Cod sursa (job #2722913)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
const int NMAX = 100001;
int n, dp[NMAX], arr[NMAX], tree[NMAX], maxxIndex;
void reconstruct(int index) {
if(index == -1)
return;
reconstruct(tree[index]);
g << arr[index] << ' ';
}
int main() {
f >> n;
for(int i = 1;i <= n;++i)
f >> arr[i], tree[i] = -1;
dp[1] = 1;
for(int i = 2;i <= n;++i) {
dp[i] = 1;
for (int j = 1; j < i; ++j) {
if (arr[j] < arr[i] && dp[i] < 1 + dp[j]) {
dp[i] = 1 + dp[j];
tree[i] = j;
}
}
if(dp[maxxIndex] < dp[i])
maxxIndex = i;
}
g << dp[maxxIndex] << '\n';
reconstruct(maxxIndex);
return 0;
}