最大子阵列和模M

Question

我们大多数人都熟悉最大和子阵列问题.我遇到了这个问题的一个变体,要求程序员输出模数为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

我们可以这样做:

维护一个sum索引处的数组ith,它包含从0到0的模数和ith.

对于每个索引ith,我们需要找到以此索引结尾的最大子总和:

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

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

因此,我们只能实现大于sum[i]if 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)

Answer 2

设A是我们的输入数组,具有从零开始的索引.我们可以在不改变结果的情况下减少A模数M.

首先,让我们通过计算代表A,模M的前缀和的数组P来将问题简化为更容易的问题:

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