Pagini recente » Cod sursa (job #2727494) | Cod sursa (job #2837606) | Cod sursa (job #3219026) | Cod sursa (job #2809572) | Cod sursa (job #2909280)
#include <iostream>
#include <array>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int maxim;
int max_poz;
int previous_poz[100000];
void max_subseq(int *arr, int n){
int N = n;
int DP[100000];
DP[0] = 1;
previous_poz[0] = -2;
for(int i = 1; i < N; ++i){
DP[i] = 1;
previous_poz[i] = -1;
for(int j = 0 ; j < i; ++j)
if(arr[i] > arr[j])
if(DP[j] + 1 > DP[i]){
DP[i] = DP[j] + 1;
previous_poz[i] = j;
if(maxim < DP[i]){
maxim = DP[i];
max_poz = i;
}
}
}
}
int main(void){
int arr[100000];
int n = 0;
f >> n;
for(int i = 0; i < n; ++i)
f >> arr[i];
max_subseq(arr,n);
g << maxim << '\n';
int pozitii[100000];
int k = 0;
for(int i = max_poz; i > -1; i = previous_poz[i]) pozitii[k++] = i;
for(int i = k-1; i > -1; --i)
g << arr[pozitii[i]] << ' ';
}