C++でのmを法とする最大サブアレイ合計

この問題では、サイズnと整数mの配列が与えられます。私たちのタスクは、C++でmを法とする最大のサブ配列の合計を見つけるプログラムを作成することです。

プログラムの説明 −ここでは、サブアレイのすべての要素の合計をmで割った値を求めます。

問題を理解するために例を見てみましょう

入力 −配列={4、9、2} m =6

出力 − 5

説明 −すべてのサブ配列と除算の余り

{4}: 4%6 = 4
{9}: 9%6 = 3
{2}: 2%6 = 2
{4, 9}: 13%6 = 1
{9, 2}: 11%6 = 5
{4, 9, 2}: 15%6 = 3

この問題を解決するために、prefixSumModulo配列を計算します。そして、式を使用して各インデックスのmaxSumを計算します。maxSumat i =（prefixi + prefixj + m）％m

例

ソリューションを説明するプログラム

#include<bits/stdc++.h>
using namespace std;
int calcMaxSum(int arr[], int n, int m) {
   int x, prefix = 0, maxSumMod = 0;
   set<int> sums;
   sums.insert(0);
   for (int i = 0; i < n; i++){
      prefix = (prefix + arr[i])%m;
      maxSumMod = max(maxSumMod, prefix);
      auto it = sums.lower_bound(prefix+1);
      if (it != sums.end())
         maxSumMod = max(maxSumMod, prefix - (*it) + m );
      sums.insert(prefix);
   }
   return maxSumMod;
}
int main() {
   int arr[] = {4, 9, 2};
   int n = sizeof(arr)/sizeof(arr[0]);
   int m = 5;
   cout<<"Maximum subarray sum modulo "<<m<<" is "<<calcMaxSum(arr, n, m) < endl;
   return 0;
}

出力

Maximum subarray sum modulo 5 is 4