# Maximum subarray problem in JavaScript

I am new to JavaScript. I've recently completed first 10 Chapters of "JavaScript: The Good Parts".

I've coded this small program to find maximum subarray of an array and would appreciate your feedback on the structure of the program (from JavaScript's point of view). I am basically looking for suggestions in following areas:

1. Objects being returned
2. Usage of Infinity
3. Usage of non-pure functions
4. Closures

Here is the code:

// Max. subarray from CLRS
var maxsubarr = function (arr) {
var that  = {};

var max_cross_subarr = function (low, mid, high) {
var left_sum = -Infinity;
var right_sum = -Infinity;
var max_low;
var max_high;

var sum = 0;
var i;
for (i=mid; i >=low; i--) {
sum = sum + arr[i];
if (sum > left_sum) {
left_sum = sum;
max_low = i;
}
}
sum = 0;
for (i=mid+1; i <=high; i++) {
sum = sum + arr[i];
if (sum > right_sum) {
right_sum = sum;
max_high = i;
}
}

return {
low: max_low,
high: max_high,
sum: left_sum + right_sum
};
}

var max_sub_arr = function (low, high) {
var leftarr, rightarr, mid;
if (low === high) {
return {
low: low,
high: high,
sum: arr[low]
};
}
else {
mid = Math.floor((high+low)/2);
leftarr = max_sub_arr (low, mid);
rightarr = max_sub_arr (mid+1, high);
crossarr = max_cross_subarr (low, mid, high);

if (leftarr.sum >= rightarr.sum && leftarr.sum >= crossarr.sum) {
return leftarr;
} else if (rightarr.sum >= leftarr.sum && rightarr.sum >= crossarr.sum) {
return rightarr;
} else {
return crossarr;
}
}
}

that.find = function () {
return max_sub_arr (0, arr.length - 1);
}

return that;
}

var mb = maxsubarr ([13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]);
console.log(mb.find());


1. Objects being returned.

This is fine as long as you define a convention and stick to it.

1. Usage of Infinity

Your use case looks fine, you're using it as an upper and lower bound.

1. Usage of non-pure functions

This one is a little subjective. For an algorithm like this, it makes sense to only write pure functions as that can make debugging easier. Your code is readable and clear, if a little contrived, but I wouldn't worry too much about this. JavaScript is sort of a weird language to ask this about since most functions won't follow this rule especially when you do DOM manipulation and frontend JavaScript.

1. Closures

Very common in JavaScript. You should explore node.js if you're interested in learning more.

Nit: var that = {};. Aside from being a completely uninformative and useless variable name, this declaration isn't needed. You can rewrite the return statement as:

return {
find: function() {
return max_sub_arr(0, arr.length - 1);
}
};


Or even better:

return max_sub_arr(0, arr.length - 1);


I don't see why you need to return a function to be invoked.

In addition to the other answer, I'd like to mention numerous function calls constituting a significant performance bottleneck, missing declaration of crossarr and therefore it's global presence on the window object, atypical naming convention and unreasonable architecture aimed at providing the unnecessary .find() function. Also, you miss 4 semicolons.

## My rewrite

• It has $O(n)$ linear complexity;
• There are no function calls in it, which significantly contributes to it's performance;
• Use of temp and result objects results in high readability and more concise code.
const maxSubarray = arr => {
const temp = {start: 0, sum: 0};
let result = {start: 0, end: 0, sum: 0};

for (let i = 0; i < arr.length; i++) {
temp.sum += arr[i];

if (temp.sum > result.sum) {
result = {start: temp.start, end: i, sum: temp.sum};
}

if (temp.sum < 0) {
temp.sum = 0;
temp.start = i + 1;
}
}

return result;
};