Pagini recente » Cod sursa (job #2708924) | Cod sursa (job #1653875)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int v[100], subsir[100], n;
int celMaiLungSubsirOrdonat(int v[] , int n , int subsir[]){
int lungime, inceput, i, j;
int *maxime = new int[n];
int *urmatorul = new int[n];
maxime[n - 1] = 1;
urmatorul[n - 1] = -1;
for(i = n - 2; i >= 0; i--){
maxime[i] = 1;
urmatorul[i] = -1;
for(j = i + 1; j < n; j++)
if(v[i] < v[j] && maxime[i] <= maxime[j]){
maxime[i] = maxime[j] + 1;
urmatorul[i] = j;
}
}
lungime = maxime[0];
inceput = 0;
for(i = 1; i < n; i++)
if(lungime < maxime[i]){
lungime = maxime[i];
inceput = i;
}
subsir[0] = v[inceput];
for(i = 1; i < lungime; i++){
inceput = urmatorul[inceput];
subsir[i] = v[inceput];
}
delete urmatorul;
delete maxime;
return lungime;
}
int main(){
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> v[i];
int l = celMaiLungSubsirOrdonat(v , n , subsir);
fout << l << '\n';
for(int i = 1; i <= l; ++i)
fout << subsir[i] << " ";
return 0;
}