Algoritmo más rápido para la función de JavaScript llamada dentro de una función

He escrito una función y he llamado a otra función dentro, pero mis pruebas muestran que no está optimizada en el tiempo. ¿Cómo puedo hacer el siguiente código más rápido?

function maxSum(arr, range) { function sumAll(array1, myrange) { var total = 0; if (Array.isArray(myrange)) { for (var i = myrange[0]; i <= myrange[1]; i++) { total += array1[i]; } return total; } else return array1[myrange]; } var mylist = []; var l = range.length; for (var n = 0; n < l; n++) { mylist.push(sumAll(arr, range[n])); } return Math.max.apply(null, mylist); } 

Código de trabajo completo basado en la excelente optimización de @ MBo. Esto pasa todas las pruebas en https://www.codewars.com/kata/the-maximum-sum-value-of-ranges-challenge-version/train/javascript , de los cuales reconozco de dónde viene este problema.

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

Optimización algorítmica: cree una nueva matriz con sums acumuladas del índice 0 a cada índice

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

Ahora no necesita calcular sums para cada rango, solo obtenga la diferencia

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

en tus términos:

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

ejemplo:

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

PD: si su matriz puede actualizarse, considere la estructura de datos del árbol de Fenwick

1) Puede definir la función sumAll fuera de la función maxSum porque cada vez que llama a maxSum el motor javascript está recreando una nueva función sumAll .

2) Puede definir myrange[1] como una variable en la parte inicializadora para evitar que javascript busque myrange[1] en cada iteración.

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

conviértete en esto:

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