資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中模 m 的最大子陣列和
在這個問題中，我們給定了一個大小為 n 的陣列和一個整數 m。我們的任務是建立一個程式，在 C++ 中找到模 m 的最大子陣列和。
程式說明 - 在這裡，我們將找到最大值，該值是透過將子陣列中所有元素的和除以 m 獲得的。
我們透過一個例子來理解這個問題，
輸入 - array = {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 陣列。並使用公式計算每個索引的最大和，即第 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
更新於： 03-06-2020
356 次瀏覽
廣告