Pagini recente » Cod sursa (job #633125) | Cod sursa (job #1813175) | Cod sursa (job #1669608) | Cod sursa (job #295739) | Cod sursa (job #537115)
Cod sursa(job #537115)
#include <stdio.h>
#include <stdlib.h>
long data[5001];
long lungime[5001];
long back[5001];
long * getSolutie( int i ){
long * ret = NULL;
ret = malloc(lungime[i]*sizeof(long));//[ lungime[i]];
int j;
long aux = i;
for ( j=lungime[i]-1; j>=0; j--){
ret[j] = aux+1;
aux = back[aux];
}
return ret;
}
int main(){
int n;
FILE * in = fopen("subsir2.in","r");
FILE * out = fopen("subsir2.out","w");
fscanf(in,"%d",&n);
int i,j;
for ( i=0; i<n; i++){
fscanf(in,"%ld",&data[i]);
}
for ( i=0; i<n; i++){
lungime[i] = 1;
back[i] = -1;
for ( j=0; j<i-1; j++){
if ( data[j]<data[i]){
if ( lungime[j]+1==lungime[i]){
if ( back[i]>=0 && data[j]<data[ back[i] ]){
back[i] = j;
}
}
if ( lungime[j]+1>lungime[i]){
lungime[i]= lungime[j]+1;
back[i] = j;
}
}
}
}
long lungimeMaxima = 0;
long * maxSol = NULL;
for ( i=0; i<n; i++){
if ( lungime[i] > lungimeMaxima){
lungimeMaxima = lungime[i];
maxSol = getSolutie( i );
}
}
for ( i=0; i<n; i++){
if ( lungime[i] == lungimeMaxima ){
long * aux = getSolutie(i);
for ( j=0; j<lungimeMaxima; j++){
if ( data[ aux[j]]==data[maxSol[j]]){
continue;
}
if ( data[ aux[j]]<data[maxSol[j]] ){
maxSol = aux;
break;
}
if ( data[ aux[j]]>data[maxSol[j]] ){
break;
}
}
}
}
fprintf(out,"%ld\n",lungimeMaxima);
for ( i=0; i<lungimeMaxima; i++){
fprintf(out,"%ld ",maxSol[i]);
}
fclose( out );
fclose(in);
return 0;
}