Pagini recente » Cod sursa (job #2083275) | Cod sursa (job #99501) | Cod sursa (job #1192578) | Cod sursa (job #1866126) | Cod sursa (job #2333679)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int n, i, maxim, j, poz, k;
int v[100005], t[100005], d[100005], sol[100005];
int main(){
fin >> n;
for (i=1; i<=n; i++){
fin >> v[i];
}
v[++n] = INT_MAX;
d[1] = 1;
for (i=2; i<=n; i++){
maxim = 0;
for (j=1; j<i; j++){
if (v[j] < v[i] && d[j] > maxim){
maxim = d[j];
poz = j;
}
}
if (maxim != 0){
d[i] = maxim + 1;
t[i] = poz;
}
else{
d[i] = 1;
t[i] = 0;
}
}
while (n){
sol[++k] = v[n];
n = t[n];
}
fout << k - 1 << " \n";
for (i=k; i>1; i--){
fout << sol[i] << " ";
}
return 0;
}
// solutie in O(n^2)
/** recapitulare **/