Pagini recente » Cod sursa (job #2329024) | Cod sursa (job #1514449) | Cod sursa (job #2978686) | Cod sursa (job #1067992) | Cod sursa (job #711321)
Cod sursa(job #711321)
#include <cstdio>
using namespace std;
#define NMAX 100000
int A[NMAX], dp[NMAX], prev[NMAX], N;
void solve(){
dp[0] = 1;
prev[0] = -1;
for(int i = 1; i < N; ++i){
int p, max = -1;
for(int j = 0; j < i; ++j)
if(A[i] > A[j] && ((dp[j] + 1) > max)){
max = dp[j] + 1;
p = j;
}
if(max != -1){
dp[i] = max;
prev[i] = p;
}
else{
dp[i] = 1;
prev[i] = -1;
}
}
}
void print_rec(int pos){
if(prev[pos] != -1)
print_rec(prev[pos]);
printf("%d ", A[pos]);
}
void print_solution(){
int posmax, max = 0;
for(int i = 0; i < N; ++i)
if(dp[i] > max)
max = dp[i], posmax = i;
printf("%d\n", max);
print_rec(posmax);
}
int main(){
freopen("scmax.in", "rt", stdin);
freopen("scmax.out", "wt", stdout);
scanf("%d", &N);
for(int i = 0; i < N; ++i)
scanf("%d", &A[i]);
solve();
print_solution();
return 0;
}