找到連續子集的最大總和，具有不同的條件

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）時間。

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更好的解決方案。所以所有可能的起點數字都必須是遞增的。

同樣，所有可能的終點上的數字也必須上升。

然後我們可以使用兩個迭代器找到最佳答案。一個迭代器遍歷所有可能的起點，另一個迭代器繼續前進，直到滿足要求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; 
} 

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's total: 
     record details on our new best candidate 
Our best candidate is the final answer.