Max Subarray (PLEASE WRITE CODE IN C++) In this lab assignment, your job is to i
ID: 3752823 • Letter: M
Question
Max Subarray (PLEASE WRITE CODE IN C++)
In this lab assignment, your job is to implement the O(n log n) time divide-and-conquer algorithm for the Max Subarray Problem; for the pseudo-code, see page 72 in the textbook. Recall that in the problem, we are given as input an array A[1 · · · n] of n integers, and would like to find i and j (1 i j n) such that A[i ] + A[i + 1] + · · · + A[j ] is maximized.
HERE IS THE PSEUDOCODE
Please write this in C++ using this pseudocde
Max Subarray In this lab assignment, your job is to implement the O(n log n) time divide-and-conquer algorithm for the MAX SuBARRAY PROBLEM; for the pseudo-code, see page 72 in the textbook. Recall that in the problem, we are given as input an array A n of n integers, and would like to find i and j' (1sisj such that AiAi1+Aj is maximized Input structure The input starts with an integer number n, which indicates the array size. Then, the integers, AllI, Al2,Alnl, follow, one per line Output the sum of integers in the max subarray, ie., Ali"] + Ali, + Output structure .+Ai] +Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include<limits.h>
long int max_subarray(long int *,int,int);
long int max_cross_subarray(long int *,int,int,int);
int main()
{
int t,zero,i,min_neg,count;
long int n,*arr,non_cont_sum;
printf("Enter the number of test cases ");
scanf("%d",&t);
while(t--)
{
printf("Enter the number of elements in the subarray ");
scanf("%ld",&n);
arr=(long int *)malloc(n*sizeof(long int));
printf("Enter the elements in the subarray ");
for(i=0;i<n;i++)
scanf("%ld",&arr[i]);
printf("Max sum of subarray is %ld ",max_subarray(arr,0,n-1));
}
return 0;
}
long int max_subarray(long int *arr,int low,int high)
{
if(high==low)
return arr[low];
int mid=(low+high)/2;
int left_sum,right_sum,cross_sum;
left_sum=max_subarray(arr,low,mid);
cross_sum=max_cross_subarray(arr,low,mid,high);
right_sum=max_subarray(arr,mid+1,high);
if(left_sum>=right_sum && left_sum>=cross_sum)
return left_sum;
else if(right_sum>=left_sum && right_sum>=cross_sum)
return right_sum;
else
return cross_sum;
}
long int max_cross_subarray(long int *arr,int low,int mid,int high)
{
int i;
long int left_sum=LONG_MIN,right_sum=LONG_MIN,sum=0;
for(i=mid;i>=low;i--)
{
sum+=arr[i];
if(sum>left_sum)
left_sum=sum;
}
sum=0;
for(i=mid+1;i<=high;i++)
{
sum+=arr[i];
if(sum>right_sum)
right_sum=sum;
}
return (left_sum+right_sum);
}