Given an array of both positive and negative integers, this function will find the largest sum of contiguous subarray.
Example
INPUT:
arr[] = {3, -4, 6, 2, -1 }
OUTPUT:
8
subarray is {6, 2}
Time Complexity: O(nlogn)
Algorithm
1. Divide the array into two halves
2. Recursively find the maximum subarray sum for left subarray
3. Recursively find the maximum subarray sum for right subarray
4. Find the maximum subarray sum that crosses the midpoint
5. return the maximum of above three sums
C++ Program
#include <bits/stdc++.h>
#include <limits>
using namespace std;
int max(int a, int b)
{
if (a>b)
{
return a;
}
else
{
return b;
}
}
//Is a recursive method, which returns maximum sum subarray
int maxSubArraySum(int arr[], int low, int high)
{
//
if (low == high)
{
return arr[low];
}
int mid = (low+high)/2;
//recursivley find left subarray
int leftsubarray = maxSubArraySum(arr, low, mid);
//recursively finding right subarray
int rightsubarray = maxSubArraySum(arr, mid+1, high);
int left_sum = INT_MIN, right_sum = INT_MIN;
int sum =0;
//Finding the left sum
for (int i = mid; i <high ; ++i)
{
sum = sum + arr[i];
right_sum = max(right_sum, sum);
}
sum =0;
//Finding the right sum
for (int i = low; i < mid; ++i)
{
sum = sum + arr[i];
left_sum = max(left_sum, sum);
}
int ans = max(leftsubarray,rightsubarray);//maximum of left and right subarray
return max(ans,left_sum+right_sum);//maximum of ans and subarray paasing through mid
}
int main()
{
int arr[]= {5, -4, 6, -1 }; //creating an array
int n = sizeof(arr)/sizeof(arr[0]); //size of the array
int low = 0, high = n-1;
cout<<"maximum subarray sum is"<<maxSubArraySum(arr,low,high);
return 0;
}