Pagini recente » Cod sursa (job #1734065) | Cod sursa (job #1940375) | Cod sursa (job #1402271) | Cod sursa (job #2615898) | Cod sursa (job #2985790)
#include <algorithm>
#include <fstream>
#include <iostream>
#define r inFile
#define w outFile
const int NMAX = 1e5;
int n;
int a[1 + NMAX];
int prev[1 + NMAX];
int dp[1 + NMAX];
void printPath(int i, std::ostream &str) {
if (i == 0) {
return;
}
printPath(prev[i], str);
str << a[i] << ' ';
}
int main() {
std::ifstream inFile("scmax.in");
std::ofstream outFile("scmax.out");
r >> n;
for (int i = 1; i <= n; ++i) {
r >> a[i];
}
// dp[i] - longest str. increasing subarray ending at position i
dp[1] = 1;
prev[1] = 0;
for (int i = 2; i <= n; ++i) {
dp[i] = 1;
for (int j = 1; j <= n; ++j) {
if (a[j] < a[i] && dp[j] >= dp[i]) {
dp[i] = 1 + dp[j];
prev[i] = j;
}
}
}
int ans = -1;
for (int i = 1; i <= n; ++i) {
if (dp[i] > dp[ans]) {
ans = i;
}
}
w << dp[ans] << '\n';
printPath(ans, w);
return 0;
}