Pagini recente » Cod sursa (job #1579829) | Cod sursa (job #2960659) | Statistici Voicu Andrei (andreivoicu4) | Cod sursa (job #1804083) | Cod sursa (job #1676594)
#include <iostream>
#include <cstdio>
using namespace std;
int v[5001];
int lungimi[5001];
int pre[5001];
int subsir[5001];
bool eCapat[5001];
int main()
{
FILE *fin = fopen("subsir2.in", "r");
FILE *fout = fopen("subsir2.out", "w");
int n, lmin, poz, k;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; ++i)
fscanf(fin, "%d", &v[i]);
lungimi[1] = 1;
for(int i = 1; i <= n; ++i){
eCapat[i] = true;
for(int j = i + 1; j <= n; ++j){
if(v[i] < v[j]){
eCapat[i] = false;
if(lungimi[i] + 1 > lungimi[j] || (lungimi[i] + 1 == lungimi[j] && v[i] < v[pre[j]])){
lungimi[j] = lungimi[i] + 1;
pre[j] = i;
}
}
}
}
poz = lmin = 0;
for(int i = 1; i <= n; ++i){
if(eCapat[i] && (poz == 0 || lungimi[i] < lmin || (lungimi[i] == lmin && v[i] < v[poz]))){
lmin = lungimi[i];
poz = i;
}
}
fprintf(fout, "%d\n", lmin);
k = 0;
while(poz != 0){
subsir[++k] = poz;
poz = pre[poz];
}
for(int i = lmin; i >= 1; --i)
fprintf(fout, "%d ", subsir[i]);
return 0;
}