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