maxSubSum_N.js

function maxSubSum(arr) {
  var maxSum = 0, thisSum = 0;
  for (i = 0; i < arr.length; i++) {
    thisSum += arr[i];
    if (thisSum > maxSum)
      maxSum = thisSum;
    else if (thisSum < 0)
      thisSum = 0;
  }
  return maxSum;
}


var arr = [4, -3, 5, -2, -1, 2, 6, -2];
maxSubSum(arr) // output: 11

maxSubSum_NlogN.js

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