最大値アルゴリズムを最適化する方法

Question

数値の配列と範囲の配列をとるこの関数があります。範囲は数値の配列のインデックスを示します。各範囲の合計について、私は最大値を返すことになっています。私は解決策を持っていますが、それをより迅速に処理するために最適化したいと考えています。ここに私の現在のソリューションは次のようになります。それは、最適化する方法を説明し、任意の答えがいただければ幸いです

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

：

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

そして、ここでは、関数に渡される引数は、いくつかのサンプルです！

Answer 1

各範囲の合計を計算するためにセグメントツリーを使用することができます。セグメントツリーの構築にはO（n * logn）時間がかかり、各クエリはO（logn）時間かかるでしょう。
http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
は今、あなたはここであなたが更新しない包み

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

セグメントツリー実装するJavaScriptコードは（n^2）最悪のケースの複雑さOを持つすべての範囲のインデックスをループしています合計配列を合計配列として事前に計算することができます

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] 

Answer 2

あなたが得る最良の最適化が何であっても、理解できるものはO（n^2）です。これは、最初の配列を1回走査して合計値を取得する必要があるからです。いくつかの配列要素をスキップしない限り、O（n^2）