Кадане с изюминкой

Question

Проблема:
Дано два массива A а также Bоба размера nнайти интервал [i,j] (0 <= i,j <= n-1) что максимизирует значение V = sum(A[i:j]) - min(B[i:j]),

Без массива B Твист, эта проблема является просто проблемой максимальной суммы подрешетки, разрешимой в 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  

Тривиальный алгоритм состоит в том, чтобы сделать двойной цикл для расчета каждого (i,j) интервал, но этот наивный подход имеет O(N^2) сложность времени.

Я пытался найти O(N)или хотя бы O(NlogN) алгоритм, но я пока не смог его достичь.

Буду признателен за любые идеи по этому поводу, спасибо!

Изменить: Реализация решения Петра для справки:

#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

Answer 1

Алгоритм Кадане вычисляет максимальную сумму окончания A в каждой позиции (назовите это F[i]).

Вы также можете запустить алгоритм Кадана в обращенном массиве A, чтобы найти максимальную сумму A, начиная с каждой позиции (назовите это R[i]).

Затем мы можем использовать эти два массива для вычисления максимальной суммы подмассива A[i:j]-B[k], где i<=k<=j для каждой позиции k (просто вычисляя F[k-1] + A[k] ] + R[k+1] - B[k] для каждого k).

Тогда это решило немного другую проблему "Найти интервал i: j, который удовлетворяет i<=k<=j и который максимизирует A[i:j] - B[k]". Однако самое высокое значение, которое это принимает, будет таким же, как при выборе B [k] в качестве минимума B[i:j], так что это эквивалентно вашей исходной задаче.

Сложность этого подхода O(n).