寻找具有不同条件的连续子集的最大和

Question

我找不到与我正在处理的特定问题相关的问题。因此，问题是在一个数组中找到具有最大总和的连续子集，但子集的第一个整数应该比它的最后一个整数大，并且时间复杂度应为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)时间内完成。

- Eliran Ziv

---

数组中的所有数字都是正数吗？ - AnotherGeek

我考虑了你说的话，但是如果我在每次迭代中添加行 "if（arr [startingIndex]> arr [endingIndex]）"，那么我的示例中的数字2永远不会比集合中的其他数字更大，因此输出将仅为2。那将是一种不正确的解决方案。 - Eliran Ziv

大于还是大于等于？我的意思是，如果数组以一个很大的负数结尾，后面跟着一个非常大的正整数，答案只能是正整数，还是必须是一个区间？ - farzadshbfn

@farzadshbfn，答案不能是单个整数，正如所提到的那样，这会违反要求。 - Eliran Ziv

@EliranZiv 我们可以有“负子集”吗？我有一个O(n)的解决方案，可以在开始位置之后找到一个起始位置。在这种情况下，它会减去中间的数字。 - btilly

Answer 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更好。因此，所有可能的起始点上的数字必须是升序的。

同样，所有可能的结束点上的数字也必须是升序的。

然后，我们可以使用两个迭代器找到最佳答案。一个迭代器遍历所有可能的起始点，另一个迭代器一直向前走，直到满足要求第一个整数应大于其最后一个整数的最后一个可能的结束点。

c++代码：

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;
}

- Mo Tao

---

谢谢您的想法。您能否发布一些代码或伪代码？我不确定如何应用它。 - גלעד ברקן

谢谢，非常棒的解决方案！ - גלעד ברקן

Answer 2

这里是针对所有数字，包括负数的 O(n log(n))。我相信它的平均性能是 O(n log(log(n)))。

我们需要一个名为 best_starts 的辅助数据结构。它将按值排序存储有关间隔可能起始点的信息。对于每个点，我们需要知道 (位置、值、运行总和)，其中 位置 是其在数组中的位置，值 是那里的值，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's total:
        record details on our new best candidate
Our best candidate is the final answer.

- btilly

---

谢谢，我希望你能发布你评论的想法。看到实际代码（不包括树的代码）会很有帮助。我感到困惑，例如在伪代码中位置如何发挥作用等问题。 - גלעד ברקן

@גלעדברקן 位置的唯一作用是跟踪，以便您可以将其作为最佳候选人的一部分进行报告。 - btilly

一个序列的开头是否大于结尾的确定在哪里进行？ - גלעד ברקן

当我们查看“下一个最大值的running_total”时，我们保证在序列中查看比我们更大的元素。 更好的是，它是与我们一起形成间隔的最佳候选者。 （那些高于它的具有更高的“running_total”，因此不会产生像那个那么大的总和。不在该数据结构中的那些严格劣于其中的那些。） - btilly