最大的子数组是模 M

Question

我们大多数人都熟悉 maximum sum subarray problem。我遇到了这个问题的一个变体，它要求程序员输出所有子数组总和的最大值以某个数字 M 为模。

解决这个变体的天真的方法是找到所有可能的子数组和（这将是 N^2 的数量级，其中 N 是数组的大小）。当然，这还不够好。问题是——我们怎样才能做得更好？

示例：让我们考虑以下数组：

6 6 11 15 12 1

令 M = 13。在这种情况下，子数组 6 6（或 12 或 6 6 11 15 或 11 15 12）将产生最大总和 ( = 12 )。

Answer 1

设 A 为我们的输入数组，索引从零开始。我们可以减少 A 模 M 而不改变结果。

首先，让我们通过计算一个数组 P 来将问题简化为一个稍微简单的问题，该数组表示 A 的前缀和，模 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

全局最大值也会出现在一个点上。由于我们可以从右到左插入后缀值，我们现在将问题简化为以下内容：

Given a set of values S and integers x and M, find the maximum of S + x modulo M

这个很简单：只需使用平衡二叉搜索树来管理 S 的元素即可。给定一个查询 x，我们想要在 S 中找到小于 M - x[=47= 的最大值]（也就是加x时没有溢出的情况）。如果没有这个值，就用S中的最大值。两者都可以在 O(log |S|) 时间内完成。

此解决方案的总运行时间：O(n log n)

下面是一些计算最大总和的 C++ 代码。它也需要对 return 最佳子数组的边界进行一些小的调整：

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

Answer 2

我们可以这样做：

维护一个数组 sum，索引 ith，它包含从 0 到 ith 的 modulus 总和。

对于每个索引 ith，我们需要找到以该索引结束的最大子和：

对于每个子数组(start + 1 , i )，我们知道这个子数组的mod和是

int a = (sum[i] - sum[start] + M) % M

所以，只有sum[start]大于sum[i]，并且尽可能接近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)

Answer 3

总 java 实现时间复杂度为 O(n*log(n))

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);

    }

}

Answer 4

修改 Kadane algorithm 以跟踪#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))

Answer 5

这里是 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;
 }

Answer 6

根据@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";
    }
}

Answer 7

对我来说，这里的所有解释都很糟糕，因为我没有理解 searching/sorting 部分。我们如何search/sort，不清楚。

我们都知道要建prefixSum，意思是sum of all elems from 0 to i with modulo m

我猜，我们要找的很清楚。知道 subarray[i][j] = (prefix[i] - prefix[j] + m) % m（表示从索引 i 到 j 的模和），当给定 prefix[i] 时，我们的最大值始终是尽可能接近 prefix[i] 但略大的 prefix[j]。

例如对于 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

Answer 8

正如您在 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);
    }

Answer 9

我的几点希望可以帮助人们更好地理解问题。

您不需要在模计算中添加+M，如前所述，%运算符可以很好地处理负数，因此a % M = (a + M) % M
如前所述，诀窍是构建代理总和 table 使得

proxy[n] = (a[1] + ... a[n]) % M

这样就可以将 maxSubarraySum[i, j] 表示为

maxSubarraySum[i, j] = (proxy[j] - proxy[j]) % M

实施技巧是在我们遍历元素时构建代理table，而不是先预构建然后使用。这是因为对于数组 a[i] 中的每个新元素，我们要计算 proxy[i] 并找到大于但尽可能接近 proxy[i] 的 proxy[j]（理想情况下大1 因为这会导致提醒 M - 1)。为此，我们需要使用一个聪明的数据结构来构建 proxy table，同时保持它的排序和能够快速找到最接近 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

Answer 10

我觉得我的想法与已经发布的内容一致，但以防万一 - 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
})

Answer 11

从你的问题来看，你似乎创建了一个数组来存储累积和（Prefix Sum Array），并且正在计算子数组arr[i:j]的总和为(sum[j] - sum[i] + M) % M。（arr和sum分别表示给定数组和前缀和数组）

计算每个子数组的总和得到 O(n*n) 算法。

出现的问题是——

Do we really need to consider the sum of every sub-array to reach the desired maximum?

没有！

对于 j 的值，当 sum[i] 刚好大于 sum[j] 或差值为 M - 1 时，值 (sum[j] - sum[i] + M) % M 将是最大值。 =21=]

这会将算法缩减为 O(nlogn)。

你可以看看这个解释！ https://www.youtube.com/watch?v=u_ft5jCDZXk

Answer 12

这里已经列出了很多很棒的解决方案，但我想添加一个具有 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 之间的任何元素都必须与两者之一形成更好的解决方案，这与我们最初的假设相矛盾。因此最优解一定来自排序后的列表中相邻的前缀和。

Answer 13

在 java 中使用树集实现...

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;

public class 主 {

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

}

Answer 14

这是 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;
}

最大的子数组是模 M

Maximum subarray sum modulo M

algorithm

binary-search

modulo

kadanes-algorithm