Pagini recente » Cod sursa (job #963493) | Cod sursa (job #1298219) | Cod sursa (job #826912) | Cod sursa (job #2180130) | Cod sursa (job #1206616)
#include<stdio.h>
#define N 5000
int v[N],prev[N],start[N],lg[N],ans[N];
int main(){
FILE *fin,*fout;
fin=fopen("subsir2.in","r");
fout=fopen("subsir2.out","w");
int n,i;
fscanf(fin,"%d",&n);
for(i=0;i<n;i++){
fscanf(fin,"%d",&v[i]);
prev[i]=-1;
start[i]=v[i];
lg[i]=1;
}
for(i=0;i<n;i++){
int j,lgInit=lg[i];
for(j=i-1;j>=0;j--)
if(v[j]<v[i]&&(lgInit+lg[j]>lg[i]||(lgInit+lg[j]==lg[i]&&start[j]<start[i]))){
start[i]=start[j];
prev[i]=j;
lg[i]=lgInit+lg[j];
}
}
int poz,max=-999999;
for(i=0;i<n;i++){
if(lg[i]>max||(start[i]<start[poz]&&lg[i]==max)){
poz=i;
max=lg[i];
}
else
if(lg[i]==max){
int lastDif=1,poz1=poz,poz2=i;
while(poz1!=-1){
if(v[poz1]<v[poz2])
lastDif=1;
else
if(v[poz2]<v[poz1])
lastDif=2;
poz1=prev[poz1];
poz2=prev[poz2];
}
if(lastDif==2)
poz=i;
}
}
fprintf(fout,"%d\n",max);
int c=max;
while(poz!=-1){
ans[--max]=poz;
poz=prev[poz];
}
for(i=0;i<c;i++)
fprintf(fout,"%d ",ans[i]+1);
return 0;
}