我正在尝试解决 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 算法为何有效:它是一个简单的动态规划,可以回答以下问题:
If we know the maximum sum end at index i-1, then maximum sum end at i is either append
a[i]
to the subarray yielding answer at i-1, OR not appending it
对于模运算,这是行不通的。例如:
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。因此,您的目标甚至不是找到最大总和。
这个问题可以在O(N lg N)
中解决使用 Kadane 算法的修改版本。
对于特定索引i,
让DP(i)
= 最大子数组和 % M 在 i 结束
让PS(i)
是在 i
自然你会开始思考如何找到一些j < i
其中(PS(i) - PS(j)+ M) % M
是最大的。 (假设您知道如何预计算 PS
和基本模运算)
这是核心部分:事实证明
为什么?因为看公式,如果DP(i) = max(PS(i), (PS(i) - PS(j) + M) % M
Where PS(j') is the smallest number larger than PS(i) out of all
j < i
PS(j') < PS(i)
,那么当然最好不要减去 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;
}
关于c++ - 使用 Kadane 算法求模的最大子数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45025222/