Pagini recente » Cod sursa (job #2406435) | Cod sursa (job #797307) | Cod sursa (job #2183371) | Cod sursa (job #1526250) | Cod sursa (job #3192486)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
const int NMAX = 100001;
int scmax[NMAX], v[NMAX], n;
int nexti[NMAX];
int find_scmax(int poz){
if(scmax[poz] != -1){
return scmax[poz];
}
int bestie = 1;
for(int i = poz + 1; i <= n; i++){
if(v[i] > v[poz]){
int best_scmax_for_i = find_scmax(i);
if(best_scmax_for_i + 1 > bestie){
bestie = best_scmax_for_i + 1;
nexti[poz] = i;
}
}
}
scmax[poz] = bestie;
return scmax[poz];
}
int main()
{
fin >> n;
for(int i = 1; i <= n; i++){
fin >> v[i];
scmax[i] = -1;
nexti[i] = -1;
}
int maxi = -1;
int start_i = -1;
for(int i = 1; i <= n; i++){
int temp = find_scmax(i);
if(temp > maxi){
maxi = temp;
start_i = i;
}
}
fout << maxi << "\n";
int i = start_i;
while(i != -1){
fout << v[i] << " ";
i = nexti[i];
}
return 0;
}