Найти наибольшую сумму непрерывного подмножества с различными условиями

Я не мог найти вопрос, связанный с этой конкретной проблемой, с которой я имею дело. Таким образом, проблема заключается в том, чтобы найти непрерывное подмножество в массиве с наибольшей суммой, но первое целое число подмножества должно быть больше его последнего целого числа в O (n) времени.

Например: 2 4 12 16 3 19 5 20 18 24

Выход должен быть 62, (19 5 20 18). До сих пор я придумал этот алгоритм:

  private int biggestSum(int[] arr)
    {
        int startingIndex = 0;
        int endingIndex = 1;
        int sum_so_far = arr[0];
        int sum_biggest = arr[0];
        int count = 0;
        for (int i = 1; i < arr.Length; i++)
        {
            sum_so_far += arr[i];
            count++;
            if (sum_so_far > sum_biggest)
            {
                startingIndex = i - count;
                endingIndex = i;
                sum_biggest = sum_so_far;
            }
            if (sum_so_far < 0)
            {
                sum_so_far = 0;
                count = 0;
            }

        }
        return sum_biggest;
    }

Я могу получить максимальную сумму подмножества, а также начальный индекс и конечный индекс подмножества. Как я могу продолжить? Или я должен использовать другой подход?

Спасибо.

ОБНОВЛЕНИЕ: Поскольку есть много людей, которые смотрели проблему и не решили ее, я хотел бы знать, может ли кто-нибудь доказать, что это не выполнимо в O (n) времени, хотя в вопросе четко сказано, что решение должно быть в O (n) времени.

Ответ 1

O (n) только для неотрицательных чисел.

Скажем, что массив a[0], a[1] ... a[n -1], где a[i] >= 0 для 0 <= i < n, и лучшим ответом является подмножество a[start], a[start + 1], ..., a[end].

Можно заключить, что a[i] < a[start] для 0 <= i < start, в противном случае i -> end было бы лучшим решением, чем start -> end. Таким образом, числа во всех возможных стартовых точках должны возрастать.

Аналогично, числа на всех возможных конечных точках также должны возрастать.

Тогда мы могли бы найти лучший ответ, используя два итератора. Один итератор перебирает все возможные стартовые точки, а другой продолжает идти до последней возможной конечной точки, которая удовлетворяет требованию first integer should be greater than its last integer.

С++ code:

int biggest_sum(const vector<int> &arr)
{
    int n = arr.size();
    // prefix sum
    vector<int> sum(n + 1);
    sum[0] = 0;
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + arr[i - 1];
    // possible start points
    vector<int> starts;
    starts.push_back(0);
    for (int i = 1; i < n; ++i)
        if (arr[i] > arr[starts.back()])
            starts.push_back(i);
    // possible end points
    vector<int> ends;
    ends.push_back(n - 1);
    for (int i = n - 2; i >= 0; --i)
        if (arr[i] < arr[ends.back()])
            ends.push_back(i);
    reverse(ends.begin(), ends.end());  
    // two iterators walking
    int answer = 0;
    for (int i = 0, j = 0; i < starts.size(); ++i) {
        while (j + 1 < ends.size() && arr[ends[j + 1]] < arr[starts[i]])
            ++j;
        int start = starts[i], end = ends[j];
        if (start < end && arr[start] > arr[end] && sum[end + 1] - sum[start] > answer)
            answer = sum[end + 1] - sum[start];
    }
    return answer;
}

Ответ 2

Здесь O(n log(n)) для всех чисел, включая отрицательные. В худшем случае, я считаю, что его средняя производительность O(n log(log(n))).

Нам понадобится вспомогательная структура данных с именем best_starts. Он будет хранить, сортировать по значению, информацию о возможных отправных точках интервалов. Для каждой точки нам нужно знать, (position, value, running_total), где position - это его позиция в массиве, value - это значение, а running_total - сумма всех элементов перед ним в массиве.

Это может храниться в красно-черном дереве, которое гарантирует O(log(n)) вставку, удаление и поиск ближайших значений.

Теперь вот псевдокод.

initialize best_starts to empty
initialize best candidate to an empty interval
running_total := 0
For each entry in the array:
    # Deal with best_starts first.
    If no equal or bigger value in best_starts:
        insert entry into best_starts
    Else:
        find next largest or equal value
        if its running_total > current running_total:
            while running_total of next largest or equal value >:
               remove next largest or equal value
            insert this (position, value, running_total)

    running_total := running_total + value

    # Now see if we have the best
    calculate running_total - running_total of next largest value
    If that difference > best candidate total:
        record details on our new best candidate
Our best candidate is the final answer.