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