Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Created June 23, 2014 13:47
Show Gist options
  • Save mycodeschool/8b4bcff69427c8a6f2aa to your computer and use it in GitHub Desktop.
Save mycodeschool/8b4bcff69427c8a6f2aa to your computer and use it in GitHub Desktop.
#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
Copy link

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))

@khacnghiem67
Copy link

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

@bharathkumarms
Copy link

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))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment