Pagini recente » Cod sursa (job #153996) | Cod sursa (job #3138747) | Cod sursa (job #3213467) | Cod sursa (job #2815875) | Cod sursa (job #260847)
Cod sursa(job #260847)
#include <stdio.h>
FILE *f =fopen ("scmax.in","r");
FILE *g =fopen ("scmax.out","w");
int n,v[100001],best[100001],max,pred[100001],sub;
void subsir(int start){
if (start!=0){
subsir(pred[start]);
fprintf(g,"%d ",v[start]);
}
}
int main(){
//citire
fscanf(f,"%d",&n);
for (int i=1;i<=n;i++)
fscanf(f,"%d",&v[i]);
//programarea dinamica
for (int i=1;i<=n;i++){
max=0;
for (int j=1;j<=i-1;j++){
if (v[j]<v[i] && best[j]>max){
max=best[j];
pred[i]=j;
}
}
best[i]=max+1;
}
max=0;
for (int i=1;i<=n;i++){
if (max<=best[i]) max=best[i];
sub=i;
}
fprintf(g,"%d\n",max);
for (int i=1;i<=n;i++)
printf("%d ",pred[i]);
subsir(sub);
}