Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#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;
}
@saharshjain

This comment has been minimized.

Copy link

@saharshjain saharshjain commented Jul 6, 2020

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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment