问题:
给定两个数组 A
和 B
, 尺寸均为 n
, 求区间 [i,j] (0 <= i,j <= n-1)
最大化 V = sum(A[i:j]) - min(B[i:j])
的值.
没有数组 B
扭曲,这个问题只是最大子数组和问题,可在O(N)
中解决使用 Kadane 的算法。现在,我们有了第二个数组,我们从范围中选择最小元素,并从总和中减去它。
Example:
A = [-5, 2, 3, 4, 5]
B = [-5, 1, 2, 0, -5]
Solution: 19
i=1 to j=4
2+3+4+5 - (-5) = 19
一个简单的算法是做一个双循环来计算每个(i,j)
间隔,但这种天真的方法有 O(N^2)
时间复杂度。
我一直在努力寻找 O(N)
,或者至少是一个 O(NlogN)
算法,但我还没有能够实现它。
如果有任何想法,我将不胜感激,谢谢!
编辑: Peter的解决方案实现,供引用:
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
int kadane_modified(vector<int>& A, vector<int>& B){
if(A.empty() || B.empty()) return 0;
int size = A.size();
// Backward Kadane's
vector<int> R(size);
int max_so_far = INT_MIN, max_starting_here = 0;
for (int i = size-1; i >= 0; i--)
{
max_starting_here = max_starting_here + A[i];
if (max_so_far < max_starting_here)
max_so_far = max_starting_here;
if (max_starting_here < 0)
max_starting_here = 0;
R[i] = max_starting_here;
}
// Forward Kadane's
vector<int> F(size);
max_so_far = INT_MIN; int max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + A[i];
if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
if (max_ending_here < 0)
max_ending_here = 0;
F[i] = max_ending_here;
}
// DP that combines previous results
vector<int> V(size);
for(int k = 0; k < size; k++){
if(k < size-1 & k > 0)
V[k] = A[k] + R[k+1] - B[k] + F[k-1];
else if(k == 0)
V[k] = A[k] - B[k] + R[k+1];
else if(k == size-1)
V[k] = A[k] - B[k] + F[k-1];
}
// The maximum V is our answer
int solution = INT_MIN;
for(int i = 0; i < size; i++){
if(solution < V[i]) solution = V[i];
}
return solution;
}
int main()
{
vector<int> A = {-5, 2, 3, 4, 5};
vector<int> B = {-5, 1, 2, 0, -5};
int solution = kadane_modified(A, B);
cout << solution << endl;
return 0;
}
输出:
19
最佳答案
Kadane 的算法计算在每个位置结束的 A 的最大总和(称为 F[i])。
您还可以在反向数组 A 上运行 Kadane 算法,以找到从每个位置开始的 A 的最大总和(称为 R[i])。
然后我们可以使用这两个数组来计算每个位置 k 的最大子数组和 A[i:j]-B[k],其中 i<=k<=j(通过简单地计算 F[k-1] + A[k] + R[k+1] - B[k] 对于每个 k)。
这就解决了稍微不同的问题“找到满足 i<=k<=j 并且最大化 A[i:j] - B[k] 的区间 i:j”。但是,这取的最高值将与选择 B[k] 为 B[i:j] 的最小值相同,因此这等同于您的原始问题。
这种方法的复杂度是 O(n)。
关于arrays - 卡丹的扭曲,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48736982/