Pagini recente » Cod sursa (job #1155643) | Cod sursa (job #1923745) | Cod sursa (job #1898529) | Cod sursa (job #991918) | Cod sursa (job #1665074)
#include <iostream>
#include <fstream>
using namespace std;
int v[100000], lung[100000], pred[100000];
ifstream in("scmax.in");
ofstream out("scmax.out");
void sir(int p) {
if(pred[p] != 0)
sir(pred[p]);
out << v[p] << " ";
}
int main() {
/*
* se da un sir de numere intregi. (v[1], v[2],...v[n])
* se cere un subsir strict crescator de lungime maxima
* (v[i1], v[i2], v[i3] ..., v[ik] cu i1 < i2 < i3...
* si v[i1] < v[i2] etc
* Ex
* v = 5 2 4 1 6 3 4 9 5 8 4
* ^ ^ ^ ^ ^
* ^ ^ ^ ^ ^
* lung[i] = lungimea celui mai mare subsir strict crescator
* care se termina pe pozitia i
*
* lung = (1, 1, 2, 1, 3, 2, 3, 4, 4, 5, 3)
*
* pred = (0, 0, 2, 0, 3, 2, 3, 5, 7, 9, 6)
*
*
*
*/
int n;
in >> n;
for(int i = 1; i <= n; i++)
in >> v[i];
lung[1] = 1;
pred[1] = 0;
int pmax = 1;
for(int i = 2; i <= n; i++) {
lung[i] = 0;
for(int j = 1; j < i; j++)
if(v[j] < v[i])
if(lung[j] > lung[i]) {
lung[i] = lung[j];
pred[i] = j;
}
lung[i]++;
if(lung[i] > lung[pmax])
pmax = i;
}
out << lung[pmax] << "\n";
sir(pmax);
return 0;
}