javascript - 函数内 JavaScript 函数调用的更快算法

Question

我已经编写了一个函数并在其中调用了另一个函数，但我的测试表明它没有进行时间优化。我怎样才能使下面的代码更快？

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


    }

Answer 1

算法优化:用从索引 0 到每个索引的累积和创建新数组

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

现在您不需要计算每个范围的总和 - 只需求差

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

用你的话来说:

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

例子:

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

附言如果您的数组可能已更新，请考虑 Fenwick tree数据结构