Pagini recente » Cod sursa (job #545405) | Cod sursa (job #869109) | Cod sursa (job #2126458) | Cod sursa (job #348273) | Cod sursa (job #544298)
Cod sursa(job #544298)
// http://infoarena.ro/problema/scmaxim
#include <fstream>
#include <cstring>
using namespace std;
#define maxSize 100001
ifstream in("scmax.in");
ofstream out("scmax.out");
int length,maxim,lastPosition;
int number[maxSize];
int best[maxSize];
int previous[maxSize];
void reconstruct(int position);
int main() {
in >> length;
for(int i=1;i<=length;i++) {
in >> number[i];
best[i] = 1;
previous[i] = i;
}
for(int i=2;i<=length;i++)
for(int k=1;k<i;k++)
if(number[k] < number[i] && best[i] < best[k] + 1) {
best[i] = best[k] + 1;
previous[i] = k;
if(best[i] > maxim) {
maxim = best[i];
lastPosition = i;
}
}
out << maxim << "\n";
reconstruct(lastPosition);
in.close();
out.close();
return (0);
}
void reconstruct(int position) {
// daca nu e "radacina" (pointeaza
// spre el insusi)
if(previous[position] != position)
reconstruct(previous[position]);
out << number[position] << " ";
}