我正在尝试解决hackerrank问题-最大子数组模数-此处https://www.hackerrank.com/challenges/maximum-subarray-sum/problem描述。
我很好奇这个问题能否用Kadane算法解决。

目标:给定一个由n个元素组成的整数数组和一个整数'm',确定其所有以m为模的子数组之和的最大值。

输入格式:

1)第一行包含一个整数“q”,表示要执行的查询数。每个查询的内容分为两行:

a)第一行包含两个以空格分隔的整数
描述-数组长度和模数。

b)第二行包含以空格分隔的整数,描述
数组元素。

这是我可能想到的C++代码。对于某些测试用例,它会失败(很抱歉,测试用例太大,无法在此处发布)。您能否评论/评论为什么这可能行不通?谢谢。

#include <bits/stdc++.h>

int main()
{
    uint64_t q = 0, n = 0, m = 0;

    std::cin >> q;
    std::cin >> n;
    std::cin >> m;

    while(q) {
        std::vector<uint64_t> vec;
        for (uint64_t i = 0; i < n; i++) {
            uint64_t num;
            std::cin >> num;
            vec.push_back(num);
        }
        uint64_t subArrayMax = 0;
        uint64_t maxMod = 0;
        for (uint64_t i = 0; i < n; i++) {
            // Kadane's algorithm.
            subArrayMax = std::max(subArrayMax, subArrayMax+vec[i]); // try (a+b)%m=(a%m+b%m)%m trick?
            maxMod = std::max(maxMod, subArrayMax % m);
        }
        std::cout << maxMod;
        --q;
    }
}

最佳答案

Kadane的算法在这里不起作用,因为它涉及模块化算术的属性。
首先,您必须了解Kadane算法的工作原理:这是一个简单的动态编程,它可以回答以下问题:

使用模块化算法时,这不起作用。例如:Let A = {1,2,3,4}, M = 6当然,使用Kadane的算法,最大和就是将所有元素相加,并且可以使用上面引用的思想来找到它:继续将a[i]附加到之前找到的最大和中。
但是,如果我们找到最大和%6 ,则答案是(2 + 3)%6 = 5,但不是(1 + 2 + 3)%6 = 0或(1 + 2 + 3 + 4)%6 = 4.最大最大和 并不意味着最大和%M 的最优值。因此,您的目标甚至没有找到最大和

使用改进的Kadane算法,可以在O(N lg N)中解决此问题。
对于特定索引 i
DP(i) =最大子数组总和%M在i处结束
PS(i)前缀总和%M 结尾,
自然地,您将开始思考如何找到最大j < i(PS(i) - PS(j)+ M) % M。 (假设您知道如何预先计算PS和基本的模块化算术)

这是核心部分:事实证明

为什么?因为看公式,如果是PS(j') < PS(i),那么当然最好是 NOT TO 减去PS(i)中的任何内容。
但是,如果使用PS(j') > PS(i),那么我们可以像这样重写公式:(M - x)%M,那么我们希望x = PS(j')-PS(i)尽可能小,以便(M - x)%M最大。
与Kadane的算法相同,我们会跟踪在此过程中找到的最大答案。
我们可以使用优先级队列或设置数据结构来为所有j'在线查找此类i,从而总计实现O(N lg N)。您可以在下面接受的代码中查看详细信息:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T;
set<LL> pre;
LL n, M, a[100010], ans, sum;

int main() {
    cin >> T;
    while(T--){
        ans = sum = 0;
        pre.clear();
        cin >> n >> M;
        for(int i=0; i<n;i++) cin >> a[i];
        for(int i=0; i<n; i++){
            (sum += a[i]) %= M;
            ans = max(ans, sum);
            ans = max(ans, (sum - *(pre.upper_bound(sum))+M)%M);
            pre.insert(sum);
        }
        cout << ans << endl;
    }
    return 0;
}

07-24 09:50
查看更多