Faster Algorithm For JavaScript Function Call Within A Function

I have written a function and called another function inside but my tests show that it is not time optimized. How can I make the following code faster? function maxSum(arr, ran

Solution 1:

Algorithmic optimization: create new array with cumulative sums from index 0 to every index

cumsum[0] = 0;
for (var i = 1; i <= arr.Length; i++) {
  cumsum[i] = cumsum[i-1] + arr[i-1]

Now you don't need to calculate sums for every range - just get difference

 sum for range (i..j) = cumsum[j+1] - cumsum[i];

in your terms:

    function sumAll(array1, myrange) {
            return cumsum[myrange[1]+1] - cumsum[myrange[0]];
    }

example:

arr = [1,2,3,4]
cumsum = [0,1,3,6,10]
sum for range 1..2 = 6 - 1 = 5

P.S. If your array might be updated, consider Fenwick tree data structure

Solution 2:

1) You can define the function sumAll outside of the function maxSum because every time you call maxSum the javascript engine is recreating a fresh new function sumAll.

2) You can define myrange[1] as a variable in the initialiser part to avoid javascript to look for myrange[1] at each iteration.

            for (var i = myrange[0]; i <= myrange[1]; i++) {

                total += array1[i];
            }

become this:

            for (var i = myrange[0], len = myrange[1]; i <= len; i++) {

                total += array1[i];
            }

Solution 3:

Full working code based on @MBo's excellent optimization. This passes all the tests at https://www.codewars.com/kata/the-maximum-sum-value-of-ranges-challenge-version/train/javascript, which I gather is where this problem comes from.

function maxSum(arr, ranges) {
  var max = null;

  var sums = [];
  var sofar = 0;
  for (var i = 0; i <= arr.length; i++) {
    sums[i] = sofar;
    sofar += arr[i];
  }

  for (var i = 0; i < ranges.length; i++) {
    var sum = sums[ranges[i][1]+1] - sums[ranges[i][0]];
    if (max === null || sum > max) {
      max = sum;
    }
  }

  return max;
}