Pagini recente » Cod sursa (job #101456) | Cod sursa (job #849575) | Cod sursa (job #436607) | Cod sursa (job #2446807) | Cod sursa (job #3198609)
#include <fstream>
using namespace std;
const int Vmax = 100001;
int a[Vmax], dp[Vmax], anterior[Vmax];
int main(){
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n;
fin>>n;
for(int i=1;i<=n;i++){
fin>>a[i];
}
for(int i=1;i<=n;i++){
int bestJ = 0;
int tempJ = 0;
for(int j=1;j<i;j++){
if(dp[j] >= bestJ)
tempJ = j;
bestJ = max(bestJ, dp[j]);
}
if(a[i] > a[tempJ]){
dp[i] = 1 + bestJ;
anterior[i] = tempJ;
}
else
dp[i] = 1;
}
int sol = 0;
int maxI = 0;
for(int i=1;i<=n;i++){
if(max(sol, dp[i]) > sol)
maxI = i;
sol = max(sol, dp[i]);
}
fout<<sol;
int final[Vmax];
int curent = maxI;
for(int i=1;i<=sol;i++){
final[i] = a[curent];
curent = anterior[curent];
}
fout<<'\n';
for(int i=sol;i>=1;i--)
fout<<final[i]<<" ";
return 0;
}