Kadane算法的变体

Question

Kadane算法的变体

arraysalgorithmdata-structuresdynamic-programmingkadanes-algorithm

3

问题:
给定两个大小为n的数组A和B，找到区间[i,j] (0 <= i,j <= n-1)使得V = sum(A[i:j]) - min(B[i:j])最大化。

如果没有数组B的限制，这个问题就是最大子数组和问题，可以使用Kadane算法在O(N)时间复杂度内解决。现在，我们有了第二个数组，我们选择范围内的最小元素，并从总和中减去它。

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

一个简单的算法是使用双重循环来计算每个间隔，但是这种朴素的方法的时间复杂度为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;
}

输出：

- Cihan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter de Rivaz · Accepted Answer

Kadane算法计算以每个位置结尾的A的最大和（称为F[i]）。

您还可以在反转数组A上运行Kadane算法，以找到以每个位置开头的A的最大和（称为R[i]）。

然后，我们可以使用这两个数组来计算每个位置k的最大子数组和A[i:j]-B[k]，其中i<=k<=j（通过简单地计算每个k的F[k-1]+A[k]+R[k+1]-B[k]）。

这样就解决了略有不同的问题：“找到满足i<=k<=j并最大化A[i:j]-B[k]的区间i:j”。但是，这个值取得的最高值将与选择B[i:j]的最小值相同，因此这等效于您原来的问题。

这种方法的复杂度为O(n)。