如何优化最大值算法

我有这个函数需要一个数组数组和一个范围数组。范围表示数组数组中的索引。对于每个范围的总和，我应该返回最大的值。我有一个解决方案，但想优化它来更快处理。这是我目前的解决方案：如何优化最大值算法

function maxSum(arr,range){ 
    const sums = [] 
    range.forEach(element => { 
    let sum = 0 
    for(let i = element[0]; i <= element[1]; i++) { 
     sum += arr[i] 
    } 
    sums.push(sum) 
    }) 
    return Math.max(...sums) 
}

这里是将被传递给函数的一些样本参数：

arr = [1,-2,3,4,-5,-4,3,2,1] 
range = [[1,3],[0,4],[6,8]]

任何答案，解释它是如何进行优化，将不胜感激！

来源

2017-08-04 Nic Bonetto

用'for'循环替换'.forEach（）'循环通常会加快速度。（除了性能，你可以通过用'const sums = range.map（...）'替换'.forEach（）'，然后使用'return sum'而不是调用'.push（总和）'。） – nnnnnn

说到优化，你说的是正确的运行时间？ – dawit

您可以使用分段树来计算每个范围的总和，分段树的构造将花费O（n * logn）时间，每个查询将花费O（logn）时间，您可以在这里找到一个引用
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
现在你遍历每一个具有最坏情况下的复杂度为O（n^2）范围内的指标以下是JavaScript代码来实现段树

function NumArray(nums) { 
    var tree = []; 
    build(0, nums.length - 1, 0); 
    return {sumRange, update}; 

    function sumRange(left, right) { 
     return sumUtil(0, nums.length - 1, 0); 

     function sumUtil(currLeft, currRight, treeIdx) { 
      if (left > currRight || right < currLeft) return 0; 
      if (left <= currLeft && right >= currRight) return tree[treeIdx]; 

      var mid = currLeft + ((currRight - currLeft) >> 1); 
      return sumUtil(currLeft, mid, treeIdx * 2 + 1) + 
       sumUtil(mid + 1, currRight, treeIdx * 2 + 2); 
     } 
    } 

    function update(idx, val) { 
     var diff = val - nums[idx]; 
     nums[idx] = val; 
     updateUtil(0, nums.length - 1, 0); 

     function updateUtil(left, right, treeIdx) { 
      if (idx >= left && idx <= right) { 
       tree[treeIdx] += diff; 
       if (left === right) return; 
       var mid = left + ((right - left) >> 1); 
       updateUtil(left, mid, treeIdx * 2 + 1); 
       updateUtil(mid + 1, right, treeIdx * 2 + 2); 
      } 
     } 
    } 

    function build(left, right, idx) { 
     if (left > right) return; 
     var mid = left + ((right - left) >> 1); 
     var sum = left === right ? nums[left] : 
      build(left, mid, idx * 2 + 1) + build(mid + 1, right, idx * 2 + 2); 

     tree[idx] = sum; 
     return sum; 
    } 
}

柜面你不想更新sum数组可以预先计算一个sum数组

sum[i] = sum[i-1] + element[i] 
// now the sum of l to r can be calculated as 
desired_sum = sum[r] - sum[l-1]

来源

2017-08-04 04:10:16 marvel308

据我所知不管你做什么最好的优化你可以得到的是O（n^2）。这是因为你必须遍历第一个数组一次，得到总和值。除非你打算跳过一些数组元素，否则最好的选择是O（n^2）

来源

2017-08-04 04:24:23 dawit

如何优化最大值算法

回答

相关问题