C ++のプレフィックス合計を使用したO（n）の最大サブ配列合計

問題の説明

正の整数と負の整数の配列が与えられた場合、その配列の最大サブ配列の合計を求めます

例

入力配列が− {-12、-5、4、-1、-7、1、8、-3}の場合、出力は9

アルゴリズム

• 入力配列のプレフィックス合計を計算します。

• Initialize− min_prefix_sum =0、res =-infinite

• i=0からnまでのループを維持します。 （nは入力配列のサイズです。）

  • cand =prefix_sum [i] – mini

  • キャンドの場合 がres（これまでのサブアレイの最大合計）より大きい場合は、resをcandで更新します。

  • prefix_sum [i]がmin_prefix_sum（これまでの最小プレフィックス合計）よりも小さい場合は、prefix_sum[i]でmin_prefix_sumを更新します。

• 解像度を返す

例

#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
   int minPrefixSum = 0;
   int res = numeric_limits<int>::min();
   int prefixSum[n];
   prefixSum[0] = arr[0];
   for (int i = 1; i < n; i++) {
      prefixSum[i] = prefixSum[i - 1] + arr[i];
   }
   for (int i = 0; i < n; i++) {
      res = max(res, prefixSum[i] - minPrefixSum);
      minPrefixSum = min(minPrefixSum, prefixSum[i]);
   }
   return res;
}
int main(){
   int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Result = " << maximumSumSubarray(arr, n) <<endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Result = 9