Finding Sequence of given size having maximum sum in an array

Problem Statement
Write a C program which, given an array A of n integers and an unsigned integer
k < n, finds out a sub sequence i, i + 1, · · · , i + k - 1 of length k such that the sum
A[i] + A[i + 1] + · · · + A[i + k - 1] is maximum over all such sub sequences of length k.
Make your computation as efficient as possible avoiding repetitive addition of the same
elements.
#include<stdio.h>
#include<stdlib.h>
int main()
{
  int *a,n,i,k,max_sum,pre_sum,cur_sum,max_index,index;
  max_sum=pre_sum=cur_sum=0;
  printf("enter the number of entrys \n");
  scanf("%d",&n);
  a=(int*)malloc(n*sizeof(int));
  printf("enter %d numbers \n",n);
  for(i=0;i<n;i++)
    {
      scanf("%d",&a[i]);
    }
  printf("enter the k \n");
  scanf("%d",&k);
  for(i=0;i<k;i++)
    {
      pre_sum=pre_sum+a[i];
    }
  max_index=0;
  index=1;
  max_sum=cur_sum=pre_sum;
  while(index+k<=n)
    {  
      cur_sum=cur_sum-a[index-1]+a[index+k-1];  
      if(cur_sum>max_sum)
{
          max_sum=cur_sum;
          max_index=index;
}
      index++;
    }
  printf("the seq. containing max sum is \n");
  for(i=max_index;i<max_index+k;i++)
    {
      printf("%d ",a[i]);
    }
  printf("\n");
  return 0;
}

No comments:

Post a Comment