Translate

Wednesday 6 November 2019

Data structure in c : Array problem solving for finding summation of overlapped sub array

//K maximum sums of non-overlapping contiguous sub-arrays
//Given an Array of Integers and an Integer value k, find out k non-overlapping sub-arrays which have k maximum sums.
//---- code by manish
#include<stdio.h>
main(){
//======================= user entry : array and size ================   
int a [5]={1,2,3,4,5};
int array_size=5;
//====================================================================
int no_of_sum,itr;
int i,j;
no_of_sum = array_size-1;
itr=no_of_sum-1;
while(itr!=0){
no_of_sum=no_of_sum+itr;
itr--;
}

int *sum_ptr= (int*) malloc((no_of_sum+array_size) * sizeof(int));
int *sum_ptr_loc= (int*) malloc((no_of_sum+array_size) * sizeof(int));

int *sum_ptr_new;
int *sum_ptr_loc_new;

sum_ptr_new=sum_ptr;
sum_ptr_loc_new=sum_ptr_loc;

int location;
//============================== calculating all sumation and storing into malloc mem ============================
for(i=0;i<array_size-1;i++){
 
    for(j=i+1;j<array_size;j++){
        location = i*10+j;
        *sum_ptr_loc=location;
       
       
if(j-i==1){       
*sum_ptr=a[i]+a[j];
}else{
    *sum_ptr=a[j]+*(sum_ptr-1);
}


sum_ptr++;
sum_ptr_loc++;
    }
 
}
//========================== including array into sumations   ==========================

for(i=0;i<array_size;i++){
   *sum_ptr = a[i] ;
   *sum_ptr_loc=i*10+i;

   sum_ptr++;
   sum_ptr_loc++;

 
}
//============================ sorting of sumation (selection short)    ======================
int swap,swap_loc;

for(i=0;i<(no_of_sum+array_size-1);i++){
    for(j=i+1;j<=(no_of_sum+array_size-1);j++){
        if(*(i+sum_ptr_new)<*(j+sum_ptr_new)){
           
         swap=*(i+sum_ptr_new);
         swap_loc=*(i+sum_ptr_loc_new);
       
         *(i+sum_ptr_new)=*(j+sum_ptr_new);
         *(i+sum_ptr_loc_new)=*(j+sum_ptr_loc_new);
       
       
         *(j+sum_ptr_new)=swap;
         *(j+sum_ptr_loc_new)=swap_loc;
       
           
        }
       
    }
}

//========================== printing all sumation  ========================

for(i=1;i<=(no_of_sum+array_size);i++ ){
    printf(" sum =  %d     location = %d  \n ", *sum_ptr_new,*sum_ptr_loc_new);
    sum_ptr_new++;
    sum_ptr_loc_new++;
}
free(*sum_ptr_new);
free(*sum_ptr_loc_new);

}

No comments:

Post a Comment