Pagini recente » Cod sursa (job #1405414) | Cod sursa (job #863361) | Cod sursa (job #835551) | Cod sursa (job #3030912) | Cod sursa (job #544296)
Cod sursa(job #544296)
// 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++) {
//maxim = 0;
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;
//maxim = max(maxim,best[i]);
if(best[i] > maxim) {
maxim = best[i];
lastPosition = i;
}
}
}
out << maxim << "\n";
reconstruct(lastPosition);
in.close();
out.close();
return (0);
}
void reconstruct(int position) {
if(previous[position] != position)
reconstruct(previous[position]);
out << number[position] << " ";
}