Tổng dãy con lớn nhất modulo m trong C++

Trong bài toán này, ta được cho mảng kích thước n và số nguyên m. Nhiệm vụ: viết chương trình tìm tổng dãy con lớn nhất modulo m trong C++.

Mô tả – tìm giá trị lớn nhất khi chia tổng các phần tử của dãy con cho m.

Hãy xem ví dụ:

Input – array = {4, 9 ,2} m = 6

Output – 5

Giải thích** – Tất cả dãy con và phần dư:

{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, ta tính mảng tiền tố modulo (prefixSumModulo). Tính maxSum tại mỗi chỉ số bằng công thức: maxSum tại i = (prefix_i + prefix_j + m) % m.

Ví dụ

Chương trình minh họa giải pháp:

#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<<"Tổng dãy con lớn nhất modulo "<<m<<" là "<<calcMaxSum(arr, n, m) < endl;    return 0; }

Kết quả

Tổng dãy con lớn nhất modulo 5 là 4