Pagini recente » Cod sursa (job #2127308) | Cod sursa (job #2778786) | Cod sursa (job #3184397) | Cod sursa (job #2744030) | Cod sursa (job #3184140)
#include <fstream>
using namespace std;
int n;
int v[200005];
int dp[200005];
int prev_e[200005];
int sol[200005];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main() {
f >> n;
for (int i = 1; i <= n; i++) {
f >> v[i];
}
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int Max = 0;
int prev_el = 0;
for (int j = 1; j < i; j++ ){
if (v[j] < v[i] && Max < dp[j]) {
Max = dp[j];
prev_el = j;
}
dp[i] = Max + 1;
prev_e[i] = prev_el;
}
}
g << dp[n] << '\n';
int aux = n;
int idx = 1;
while(aux != 0) {
sol[idx++] = aux;
aux = prev_e[aux];
}
for (int i = dp[n]; i >= 1; i--) {
g << v[sol[i]] << " ";
}
}