找到具有不同条件的连续子​​集的最大总和

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)时间内是不可行的,尽管问题清楚地提到解决方案应该在准时.

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]for 0 <= i < start, 否则i -> end将是比 更好的解决方案start -> end。因此所有可能的起点上的数字必须是升序的。

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

然后我们可以使用两个迭代器找到最佳答案。一个迭代器遍历所有可能的起点，另一个迭代器继续遍历，直到满足要求的最后一个可能的终点first integer should be greater than its last integer。

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