//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);
}
//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);
}
