我们大多数人都熟悉最大和子数组问题。我遇到了这个问题的一个变体，它要求程序员输出所有子数组和以某个数 M 为模的最大值。
解决这个变体的天真的方法是找到所有可能的子数组和（这将是 N^2 的数量级，其中 N 是数组的大小）。当然，这还不够好。问题是——我们怎样才能做得更好？
示例：让我们考虑以下数组：
6 6 11 15 12 1
令 M = 13。在这种情况下，子数组 6 6（或 12 或 6 6 11 15 或 11 15 12）将产生最大和（= 12）。
问问题
21971 次
14 回答
30
我们可以这样做：
sum维护一个在 index 处的数组ith，它包含从 0 到 的模数和ith。
对于每个索引ith，我们需要找到以该索引结尾的最大子和：
对于每个子数组 (start + 1 , i )，我们知道这个子数组的 mod sum 是
int a = (sum[i] - sum[start] + M) % M
所以，我们只能实现大于sum[i]如果sum[start]大于sum[i]且尽可能接近的子和sum[i] 。
如果您使用二叉搜索树，这可以很容易地完成。
伪代码：
int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
sum[i] = sum[i - 1] + A[i];
sum[i] %= M;
int a = tree.getMinimumValueLargerThan(sum[i]);
result = max((sum[i] - a + M) % M, result);
tree.add(sum[i]);
}
print result;
时间复杂度：O(n log n)
于 2015-06-29T11:50:17.620 回答
7
让A是我们的输入数组，索引从零开始。我们可以在不改变结果的情况下减少A模M。
首先，让我们通过计算一个表示A的前缀和的数组P以M为模，将问题简化为一个稍微简单的问题：
A = 6 6 11 2 12 1
P = 6 12 10 12 11 12
现在让我们按降序处理解决方案子数组的可能左边界。这意味着我们将首先确定从索引n - 1开始的最优解，然后是从索引n - 2开始的最优解，以此类推。
在我们的示例中，如果我们选择i = 3作为左边界，则可能的子数组和由后缀P[3..n-1]加上常数a = A[i] - P[i] 表示：
a = A[3] - P[3] = 2 - 12 = 3 (mod 13)
P + a = * * * 2 1 2
全局最大值也将出现在某一点。由于我们可以从右到左插入后缀值，我们现在将问题简化为以下内容：
给定一组值S和整数x和M，找到S + x模M的最大值
这很简单：只需使用平衡的二叉搜索树来管理S的元素。给定一个查询x ，我们希望找到S中小于M - x的最大值（即添加x时不会发生溢出的情况）。如果没有这样的值，只需使用S的最大值。两者都可以在 O(log |S|) 时间内完成。
此解决方案的总运行时间：O(n log n)
这是一些计算最大和的 C++ 代码。它还需要一些小的调整才能返回最佳子数组的边界：
#include <bits/stdc++.h>
using namespace std;
int max_mod_sum(const vector<int>& A, int M) {
vector<int> P(A.size());
for (int i = 0; i < A.size(); ++i)
P[i] = (A[i] + (i > 0 ? P[i-1] : 0)) % M;
set<int> S;
int res = 0;
for (int i = A.size() - 1; i >= 0; --i) {
S.insert(P[i]);
int a = (A[i] - P[i] + M) % M;
auto it = S.lower_bound(M - a);
if (it != begin(S))
res = max(res, *prev(it) + a);
res = max(res, (*prev(end(S)) + a) % M);
}
return res;
}
int main() {
// random testing to the rescue
for (int i = 0; i < 1000; ++i) {
int M = rand() % 1000 + 1, n = rand() % 1000 + 1;
vector<int> A(n);
for (int i = 0; i< n; ++i)
A[i] = rand() % M;
int should_be = 0;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j < n; ++j) {
sum = (sum + A[j]) % M;
should_be = max(should_be, sum);
}
}
assert(should_be == max_mod_sum(A, M));
}
}
于 2015-06-29T11:30:17.370 回答
3
对我来说，这里的所有解释都很糟糕，因为我没有得到搜索/排序部分。我们如何搜索/排序，尚不清楚。
我们都知道我们需要prefixSum建造sum of all elems from 0 to i with modulo m
我想，我们正在寻找的是明确的。知道这一点subarray[i][j] = (prefix[i] - prefix[j] + m) % m（表示从索引 i 到 j 的模和），当给定前缀 [i] 时，我们的最大值始终是前缀 [j]，它尽可能接近前缀 [i]，但稍大一些。
例如，对于 m = 8，prefix[i] 为 5，我们正在寻找 5 之后的下一个值，它在我们的 prefixArray 中。
为了高效搜索（二分搜索），我们对前缀进行排序。
我们不能做的是，先构建prefixSum，然后再次从0迭代到n，并在排序后的前缀数组中查找索引，因为我们可以找到小于我们的startIndex的endIndex，这是不好的。
因此，我们所做的就是从 0 迭代到 n，指示我们潜在的最大子数组和的endIndex，然后查看我们的排序前缀数组（开头为空），其中包含 0 和 endIndex 之间的排序前缀。
def maximumSum(coll, m):
n = len(coll)
maxSum, prefixSum = 0, 0
sortedPrefixes = []
for endIndex in range(n):
prefixSum = (prefixSum + coll[endIndex]) % m
maxSum = max(maxSum, prefixSum)
startIndex = bisect.bisect_right(sortedPrefixes, prefixSum)
if startIndex < len(sortedPrefixes):
maxSum = max(maxSum, prefixSum - sortedPrefixes[startIndex] + m)
bisect.insort(sortedPrefixes, prefixSum)
return maxSum
于 2018-09-14T18:39:24.820 回答
3
从您的问题来看，您似乎已经创建了一个数组来存储累积总和（前缀总和数组），并将子数组的总和计算arr[i:j]为(sum[j] - sum[i] + M) % M. （arr 和 sum 分别表示给定数组和前缀 sum 数组）
计算每个子数组的总和会产生一个O(n*n)算法。
出现的问题是——
我们真的需要考虑每个子数组的总和以达到所需的最大值吗？
不！
对于一个值，当大于或差值为时，j该值(sum[j] - sum[i] + M) % M将是最大值。sum[i]sum[j]M - 1
这会将算法减少到O(nlogn).
于 2020-06-20T07:09:42.803 回答
2
这是最大子数组和模的Java代码。我们处理在树中找不到严格大于 s[i] 的最小元素的情况
public static long maxModulo(long[] a, final long k) {
long[] s = new long[a.length];
TreeSet<Long> tree = new TreeSet<>();
s[0] = a[0] % k;
tree.add(s[0]);
long result = s[0];
for (int i = 1; i < a.length; i++) {
s[i] = (s[i - 1] + a[i]) % k;
// find least element in the tree strictly greater than s[i]
Long v = tree.higher(s[i]);
if (v == null) {
// can't find v, then compare v and s[i]
result = Math.max(s[i], result);
} else {
result = Math.max((s[i] - v + k) % k, result);
}
tree.add(s[i]);
}
return result;
}
于 2017-03-15T13:06:50.780 回答
2
我这边的几点可能希望能帮助某人更好地理解这个问题。
您不需要添加
+M到模计算中，如前所述，%运算符可以很好地处理负数，所以a % M = (a + M) % M如前所述，诀窍是构建代理总和表，使得
proxy[n] = (a[1] + ... a[n]) % M
然后，这允许将 as 表示maxSubarraySum[i, j]为
maxSubarraySum[i, j] = (proxy[j] - proxy[j]) % M
实现技巧是在我们遍历元素时构建代理表，而不是先预构建它然后使用。这是因为对于数组中的每个新元素，a[i]我们要计算proxy[i]并发现proxy[j]它大于但尽可能接近proxy[i]（理想情况下更大，1因为这会提示M - 1）。为此，我们需要使用一种巧妙的数据结构来构建proxy表格，同时保持表格的排序并能够快速找到最接近的更大元素proxy[i]。bisect.bisect_right在 Python 中是一个不错的选择。
请参阅下面的 Python 实现（希望这会有所帮助，但我知道这可能不一定像其他解决方案那样简洁）：
def maximumSum(a, m):
prefix_sum = [a[0] % m]
prefix_sum_sorted = [a[0] % m]
current_max = prefix_sum_sorted[0]
for elem in a[1:]:
prefix_sum_next = (prefix_sum[-1] + elem) % m
prefix_sum.append(prefix_sum_next)
idx_closest_bigger = bisect.bisect_right(prefix_sum_sorted, prefix_sum_next)
if idx_closest_bigger >= len(prefix_sum_sorted):
current_max = max(current_max, prefix_sum_next)
bisect.insort_right(prefix_sum_sorted, prefix_sum_next)
continue
if prefix_sum_sorted[idx_closest_bigger] > prefix_sum_next:
current_max = max(current_max, (prefix_sum_next - prefix_sum_sorted[idx_closest_bigger]) % m)
bisect.insort_right(prefix_sum_sorted, prefix_sum_next)
return current_max
于 2020-01-20T13:06:53.440 回答
2
这里已经列出了一堆很棒的解决方案，但我想添加一个具有 O(nlogn) 运行时间的解决方案，而不使用 Python 标准库中不存在的平衡二叉树。这个解决方案不是我的主意，但我不得不考虑一下它为什么起作用。这是代码，解释如下：
def maximumSum(a, m):
prefixSums = [(0, -1)]
for idx, el in enumerate(a):
prefixSums.append(((prefixSums[-1][0] + el) % m, idx))
prefixSums = sorted(prefixSums)
maxSeen = prefixSums[-1][0]
for (a, a_idx), (b, b_idx) in zip(prefixSums[:-1], prefixSums[1:]):
if a_idx > b_idx and b > a:
maxSeen = max((a-b) % m, maxSeen)
return maxSeen
与其他解决方案一样，我们首先计算前缀和，但这次我们还跟踪前缀和的索引。然后我们对前缀和进行排序，因为我们想找到前缀和之间的最小差异模 m - 排序让我们只查看相邻元素，因为它们具有最小的差异。
在这一点上，您可能认为我们忽略了问题的一个重要部分——我们希望前缀和之间的差异最小，但较大的前缀和需要出现在较小的前缀和之前（意味着它具有较小的索引）。在使用树的解决方案中，我们通过一一添加前缀和并重新计算最佳解决方案来确保。
然而，事实证明，我们可以查看相邻元素并忽略不满足索引要求的元素。这让我困惑了一段时间，但关键的实现是最优解总是来自两个相邻的元素。我将通过一个矛盾来证明这一点。假设最优解来自两个不相邻的前缀和 x 和 z，索引为 i 和 k，其中 z > x（它已排序！）且 k > i：
x ... z
k ... i
让我们考虑 x 和 z 之间的一个数字，我们称它为 y，索引为 j。由于列表已排序，因此 x < y < z。
x ... y ... z
k ... j ... i
前缀和 y 必须具有索引 j < i，否则它将成为 z 更好解决方案的一部分。但如果 j < i，则 j < k 和 y 和 x 形成比 z 和 x 更好的解！所以 x 和 z 之间的任何元素都必须与两者之一形成更好的解决方案，这与我们最初的假设相矛盾。因此最优解必须来自排序列表中相邻的前缀和。
于 2021-01-29T21:07:37.263 回答
1
使用 O(n*log(n)) 的总 Java 实现
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;
import java.util.stream.Stream;
public class MaximizeSumMod {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
Long times = Long.valueOf(in.readLine());
while(times --> 0){
long[] pair = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
long mod = pair[1];
long[] numbers = Stream.of(in.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
printMaxMod(numbers,mod);
}
}
private static void printMaxMod(long[] numbers, Long mod) {
Long maxSoFar = (numbers[numbers.length-1] + numbers[numbers.length-2])%mod;
maxSoFar = (maxSoFar > (numbers[0]%mod)) ? maxSoFar : numbers[0]%mod;
numbers[0] %=mod;
for (Long i = 1L; i < numbers.length; i++) {
long currentNumber = numbers[i.intValue()]%mod;
maxSoFar = maxSoFar > currentNumber ? maxSoFar : currentNumber;
numbers[i.intValue()] = (currentNumber + numbers[i.intValue()-1])%mod;
maxSoFar = maxSoFar > numbers[i.intValue()] ? maxSoFar : numbers[i.intValue()];
}
if(mod.equals(maxSoFar+1) || numbers.length == 2){
System.out.println(maxSoFar);
return;
}
long previousNumber = numbers[0];
TreeSet<Long> set = new TreeSet<>();
set.add(previousNumber);
for (Long i = 2L; i < numbers.length; i++) {
Long currentNumber = numbers[i.intValue()];
Long ceiling = set.ceiling(currentNumber);
if(ceiling == null){
set.add(numbers[i.intValue()-1]);
continue;
}
if(ceiling.equals(currentNumber)){
set.remove(ceiling);
Long greaterCeiling = set.ceiling(currentNumber);
if(greaterCeiling == null){
set.add(ceiling);
set.add(numbers[i.intValue()-1]);
continue;
}
set.add(ceiling);
ceiling = greaterCeiling;
}
Long newMax = (currentNumber - ceiling + mod);
maxSoFar = maxSoFar > newMax ? maxSoFar :newMax;
set.add(numbers[i.intValue()-1]);
}
System.out.println(maxSoFar);
}
}
于 2016-07-19T19:30:15.053 回答
1
根据@Pham Trung 建议的解决方案添加 STL C++11 代码。可能很方便。
#include <iostream>
#include <set>
int main() {
int N;
std::cin>>N;
for (int nn=0;nn<N;nn++){
long long n,m;
std::set<long long> mSet;
long long maxVal = 0; //positive input values
long long sumVal = 0;
std::cin>>n>>m;
mSet.insert(m);
for (long long q=0;q<n;q++){
long long tmp;
std::cin>>tmp;
sumVal = (sumVal + tmp)%m;
auto itSub = mSet.upper_bound(sumVal);
maxVal = std::max(maxVal,(m + sumVal - *itSub)%m);
mSet.insert(sumVal);
}
std::cout<<maxVal<<"\n";
}
}
于 2017-08-24T15:57:06.927 回答
1
正如您在Wikipedia中看到的那样，存在一个称为 Kadane 算法的解决方案，该算法通过在数组上迭代一次来计算最大子数组总和，观察所有位置i的最大子数组在位置i处结束。然后这解决了运行时复杂度 O(n) 的问题。
不幸的是，我认为当存在多个解决方案时，Kadane 的算法无法找到所有可能的解决方案。
Java中的一个实现，我没有测试它：
public int[] kadanesAlgorithm (int[] array) {
int start_old = 0;
int start = 0;
int end = 0;
int found_max = 0;
int max = array[0];
for(int i = 0; i<array.length; i++) {
max = Math.max(array[i], max + array[i]);
found_max = Math.max(found_max, max);
if(max < 0)
start = i+1;
else if(max == found_max) {
start_old=start;
end = i;
}
}
return Arrays.copyOfRange(array, start_old, end+1);
}
于 2019-05-21T18:24:30.207 回答
0
我觉得我的想法与已经发布的内容一致，但以防万一 - Kotlin O(NlogN) 解决方案：
val seen = sortedSetOf(0L)
var prev = 0L
return max(a.map { x ->
val z = (prev + x) % m
prev = z
seen.add(z)
seen.higher(z)?.let{ y ->
(z - y + m) % m
} ?: z
})
于 2020-02-29T15:42:10.600 回答
0
在java中使用treeset实现...
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
公共类主要{
public static void main(String[] args) throws IOException {
BufferedReader read = new BufferedReader(new InputStreamReader(System.in)) ;
String[] str = read.readLine().trim().split(" ") ;
int n = Integer.parseInt(str[0]) ;
long m = Long.parseLong(str[1]) ;
str = read.readLine().trim().split(" ") ;
long[] arr = new long[n] ;
for(int i=0; i<n; i++) {
arr[i] = Long.parseLong(str[i]) ;
}
long maxCount = 0L ;
TreeSet<Long> tree = new TreeSet<>() ;
tree.add(0L) ;
long prefix = 0L ;
for(int i=0; i<n; i++) {
prefix = (prefix + arr[i]) % m ;
maxCount = Math.max(prefix, maxCount) ;
Long temp = tree.higher(prefix) ;
System.out.println(temp);
if(temp != null) {
maxCount = Math.max((prefix-temp+m)%m, maxCount) ;
}
//System.out.println(maxCount);
tree.add(prefix) ;
}
System.out.println(maxCount);
}
}
于 2021-05-18T20:49:49.103 回答
0
这是针对此问题的 Java 解决方案的一种实现，它使用 Java 中的 TreeSet 来优化解决方案！
public static long maximumSum2(long[] arr, long n, long m)
{
long x = 0;
long prefix = 0;
long maxim = 0;
TreeSet<Long> S = new TreeSet<Long>();
S.add((long)0);
// Traversing the array.
for (int i = 0; i < n; i++)
{
// Finding prefix sum.
prefix = (prefix + arr[i]) % m;
// Finding maximum of prefix sum.
maxim = Math.max(maxim, prefix);
// Finding iterator poing to the first
// element that is not less than value
// "prefix + 1", i.e., greater than or
// equal to this value.
long it = S.higher(prefix)!=null?S.higher(prefix):0;
// boolean isFound = false;
// for (long j : S)
// {
// if (j >= prefix + 1)
// if(isFound == false) {
// it = j;
// isFound = true;
// }
// else {
// if(j < it) {
// it = j;
// }
// }
// }
if (it != 0)
{
maxim = Math.max(maxim, prefix - it + m);
}
// adding prefix in the set.
S.add(prefix);
}
return maxim;
}
于 2021-05-23T12:57:57.627 回答
-2
修改Kadane 算法以跟踪#occurrence。下面是代码。
#python3
#source: https://github.com/harishvc/challenges/blob/master/dp-largest-sum-sublist-modulo.py
#Time complexity: O(n)
#Space complexity: O(n)
def maxContiguousSum(a,K):
sum_so_far =0
max_sum = 0
count = {} #keep track of occurrence
for i in range(0,len(a)):
sum_so_far += a[i]
sum_so_far = sum_so_far%K
if sum_so_far > 0:
max_sum = max(max_sum,sum_so_far)
if sum_so_far in count.keys():
count[sum_so_far] += 1
else:
count[sum_so_far] = 1
else:
assert sum_so_far < 0 , "Logic error"
#IMPORTANT: reset sum_so_far
sum_so_far = 0
return max_sum,count[max_sum]
a = [6, 6, 11, 15, 12, 1]
K = 13
max_sum,count = maxContiguousSum(a,K)
print("input >>> %s max sum=%d #occurrence=%d" % (a,max_sum,count))
于 2016-10-01T02:09:32.600 回答