如何優化最大值算法

我有這個函數需要一個數組數組和一個範圍數組。範圍表示數組數組中的索引。對於每個範圍的總和，我應該返回最大的值。我有一個解決方案，但想優化它來更快處理。這是我目前的解決方案：如何優化最大值算法

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

如何優化最大值算法

回答

相關問題