Pagini recente » Cod sursa (job #674387) | Cod sursa (job #2819788) | Rating Dan Gutu (dan.gutu) | Cod sursa (job #2011823) | Cod sursa (job #1844094)
#include <iostream>
#include <stack>
using namespace std;
int A[100001];
int M[100001];
int Pred[100001];
int N;
void read(){
cin >> N;
for(int i=1; i<=N; i++)
cin >> A[i];
}
void showSub(int maxi){
stack<int> S;
int i = maxi;
while(i > 0){
S.push(A[i]);
i = Pred[i];
}
while(!S.empty()){
cout << S.top() << " ";
S.pop();
}
}
int main(){
freopen("scmax.in", "r", stdin);
freopen("scmax.out", "w", stdout);
read();
M[0] = 0;
M[1] = 1;
Pred[1] = 0;
int maxim = 0;
int max_pos = 0;
int maxi = 1;
for(int i=2; i<=N; i++){
maxim = 0;
max_pos = 0;
for(int j=1; j<i; j++){
if(A[j] < A[i] && M[j] > maxim){
maxim = M[j];
max_pos = j;
}
}
if(maxim + 1 > M[i-1])
maxi = i;
Pred[i] = max_pos;
M[i] = max(maxim + 1, M[i-1]);
}
cout << M[N] << "\n";
showSub(maxi);
return 0;
}