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

sumforrange(i..j)=cumsum[j+1]-cumsum[i];

in your terms:

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

example:

arr =[1,2,3,4]cumsum=[0,1,3,6,10]sumforrange1..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.

functionmaxSum(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;
}