Pagini recente » Cod sursa (job #905675) | Cod sursa (job #2239800) | Cod sursa (job #702062) | Cod sursa (job #3279117) | Cod sursa (job #741960)
Cod sursa(job #741960)
#include <cstdio>
#include <fstream>
using namespace std;
#define NMAX 100000
int A[NMAX], dp[NMAX], prev[NMAX], N;
int sol[NMAX], ctr = 0;
ifstream in("scmax.in");
ofstream out("scmax.out");
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){
sol[ctr++] = pos;
while(prev[pos] != -1){
sol[ctr++] = prev[pos];
pos = prev[pos];
}
}
void print_solution(){
int posmax, max = 0;
for(int i = 0; i < N; ++i)
if(dp[i] > max)
max = dp[i], posmax = i;
out << max << endl;
print_rec(posmax);
}
int main(){
in >> N;
for(int i = 0; i < N; ++i)
in >> A[i];
solve();
print_solution();
for(int i = ctr - 1; i >= 0; --i)
out << A[sol[i]] << " ";
return 0;
}