Maximum Subarray Problem

Using the recursive method with mss(); and the iterative method with imss(); both are O(n) and return 0 if all values are negative.

by gschutz

JavaScript

var list = [2,-5,3,4,-2,8,-4,5];

function mss(A) {
	var max = 0;
  
  function opt(j) {
  	if (j == 0)
    	return 0;
  	return Math.max(opt(j-1) + A[j], A[j]);
  }
  
  max = Math.max(opt(A.length-1), 0);
  
  return max;
}

function imss(A) {
	var max = 0, max_end = 0;
  
  A.forEach(function(a, i) {
  	max_end = Math.max(a, max_end + a);
    max = Math.max(0, max_end);
  });
  
  return max;
}

console.log(mss(list))
console.log(imss(list))