function maxSubSum(arr) {
return maxSubRec(arr, 0, arr.length - 1);
}
function maxSubRec(arr, left, right) {
if (left == right)
if (arr[left] > 0)
return arr[left];
else
return 0;
var center = Math.floor((left + right) / 2);
var maxLeftSum = maxSubRec(arr, left, center);
var maxRightSum = maxSubRec(arr, center + 1, right);
var maxLeftBorderSum = 0,
LeftBorderSum = 0;
for (var i = center; i >= left; i--) {
LeftBorderSum += arr[i];
if (LeftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = LeftBorderSum;
}
var maxRightBorderSum = 0;
RightBorderSum = 0;
for (var i = center + 1; i <= right; i++) {
RightBorderSum += arr[i];
if (RightBorderSum > maxRightBorderSum)
maxRightBorderSum = RightBorderSum;
}
return Math.max(maxLeftSum, maxLeftBorderSum + maxRightBorderSum, RightBorderSum);
}
var arr = [4, -3, 5, -2, -1, 2, 6, -2];
maxSubSum(arr); // output: 11