Mô đun tổng của mảng con tối đa m trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng kích thước n và một số nguyên m. nhiệm vụ của chúng ta là tạo một chương trình sẽ tìm modulo tổng của mảng con tối đa trong C ++.

Mô tả chương trình - Ở đây, chúng ta sẽ tìm giá trị lớn nhất có được bằng cách chia tổng tất cả các phần tử của mảng con chia cho m.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào - mảng ={4, 9, 2} m =6

Đầu ra - 5

Giải thích - Tất cả các mảng con và phần còn lại của chúng khi phân chia

{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

Để giải quyết vấn đề này, chúng tôi tính toán mảng prefixSumModulo. Và tính toán maxSum của mỗi chỉ mục bằng công thức, maxSum tại i =(prefixi + prefixj + m)% m

Ví dụ

Chương trình minh họa giải pháp của chúng tôi,

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

Đầu ra

Maximum subarray sum modulo 5 is 4