Max Subarray with indexes

by rishul matta

JavaScript

function crossSubarray(array, left, middle, right) {
    var leftSum = -Infinity;
    var rightSum = -Infinity;
    var sum = 0;
    // Include elements on left of mid
    for (var i = middle; i >= left; i--) {
      if (sum + array[i] >= leftSum) {
        leftSum = sum + array[i];
      }
      sum += array[i];
    }
    sum = 0;
    // Include elements on right of mid
    for (var i = middle + 1; i < right; i++) {
      if (sum + array[i] >= rightSum) {
        rightSum = sum + array[i];
      }
      sum += array[i];
    }
    return {
    sum: leftSum + rightSum,
    start: left,
    end: right,
    length: right - left - 1,
    };
  }

  function maxSubarrayPartitioner(array, left, right) {
    if (right - left <= 1) {
      return {
    sum: array[left],
    start: left,
    end: left,
    length: 0,
    };

    }
    var middle = Math.floor((left + right) / 2);
    var leftSum = maxSubarrayPartitioner(array, left, middle);
    var rightSum = maxSubarrayPartitioner(array, middle, right);
    var crossSum = crossSubarray(array, left, middle, right);
    return [leftSum, rightSum, crossSum].sort(function(a, b) {
		 	return a.sum > b.sum || a.length > b.length || a.start < b.start;
		}).pop();
  }
   
  function maxSubarraydivideAndConquer(array) {
  	var maxObj = maxSubarrayPartitioner(array, 0, array.length);
    return array.slice(maxObj.start, maxObj.end)
  }  

console.log(maxSubarraydivideAndConquer([1, 2, 5, -7, 2, 3]));