MaximumSumSubarray_NlogN.cpp

#include<cmath>
#include<iostream>
#include<climits>
using namespace std;

int Max_Subarray_Sum(int arr[],int n)	
{
	if(n==1)
	{
		return arr[0];
	}
	int m = n/2;
	int left_MSS = Max_Subarray_Sum(arr,m);
	int right_MSS = Max_Subarray_Sum(arr+m,n-m);
	int leftsum = INT_MIN, rightsum = INT_MIN, sum=0;
	for(int i=m;i < n; i++)
	{
		sum += arr[i];
		rightsum = max(rightsum,sum);
	}
	sum = 0;
	for(int i= (m-1);i >= 0; i--)
	{
		sum += arr[i];
		leftsum = max(leftsum,sum);
	}
	int ans = max(left_MSS,right_MSS);
	return max(ans,leftsum+rightsum);
}


int main(int argc, char const *argv[])
{
	int arr[] = {3,-2,5,-1};
	cout<<Max_Subarray_Sum(arr,4)<<"\n";
	return 0;
}

when you calculator sum left you need start to mid -1 to start.

Greetings, I was trying to achieve this in JS(Node), There is some error in my solution but couldn't figure it out properly. Kindly help me out.

function maximumSumSubarray(arr, start, end) {
  if (start == end) {
    return arr[start];
  }
  let mid = parseInt((start + end) / 2, 10);
  let leftMaxSumSubarray = maximumSumSubarray(arr, start, mid);
  let rightMaxSumSubarray = maximumSumSubarray(arr, mid + 1, end);
  let leftSum = Number.MIN_SAFE_INTEGER;
  let rightSum = Number.MIN_SAFE_INTEGER;
  let sum = 0;
  for (let i = mid; i < end; i++) {
    sum += arr[i];
    rightSum = Math.max(rightSum, sum);
  }
  sum = 0;
  for (let i = mid; i >= start; i--) {
    sum += arr[i];
    leftSum = Math.max(leftSum, sum);
  }
  let answer = Math.max(leftMaxSumSubarray, rightMaxSumSubarray);
  let toReturn = Math.max(answer, (leftSum + rightSum));
  return toReturn;
}

console.log(maximumSumSubarray([1, 2, 3, 4, -10], 0, 4))

function maximumSumSubarray(arr, start, end) {
if (start == end) {
return arr[start];
}
let mid = Math.floor((start + end) / 2);
let leftMaxSumSubarray = maximumSumSubarray(arr, start, mid);
let rightMaxSumSubarray = maximumSumSubarray(arr, mid + 1, end);
let leftSum = Number.MIN_SAFE_INTEGER;
let rightSum = Number.MIN_SAFE_INTEGER;
let sum = 0;
for (let i = mid+1; i <= end; i++) {
sum += arr[i];
rightSum = Math.max(rightSum, sum);
}
sum = 0;
for (let i = mid; i >= start; i--) {
sum += arr[i];
leftSum = Math.max(leftSum, sum);
}
let answer = Math.max(leftMaxSumSubarray, rightMaxSumSubarray);
let toReturn = Math.max(answer, (leftSum + rightSum));
return toReturn;
}

console.log(maximumSumSubarray([3,-2,5,1], 0, 3))