Pagini recente » Cod sursa (job #402404) | Cod sursa (job #130194) | Cod sursa (job #36362) | Cod sursa (job #864613) | Cod sursa (job #531178)
Cod sursa(job #531178)
#include <fstream.h>
#define N 5001
ifstream fin("subsir2.in");
ofstream fout("subsir2.out");
long long a[N], n, p[N], L[N], ValMin, idxMin,best,start,ok;
void scmax(){
int i,j;
best = 5001;
start = n;
for (i=n; i>0; i--){
L[i] = 5001; // lungimea sirului maximal i
p[i] = i; // urmatorul element dupa i
ValMin = 1000001;
ok = 0;
for (j=i+1; j<=n; j++){
if(a[i] <= a[j] && a[j]<ValMin){
ValMin = a[j];
if (L[j]+1 < L[i]){
L[i] = L[j] + 1;
p[i] = j;
ok = 1;
} else if (L[i] == L[j]+1 && a[j] < a[p[i]]){
p[i] = j;
ok = 1;
}
}
}
if (!ok) L[i] = 1;
if (a[i]<a[start]){
best = L[i];
start = i;
}
}
}
int main(){
long i,j;
fin>>n;
for (i=1;i<=n; i++)
fin>>a[i];
scmax();
fout<<L[start]<<"\n";
for (i=start,j=1;i<=L[start];i++,j=p[j])
fout<<j<<" ";
return 0;
}