查找陣列

Question

我解決一個問題CS最大的子集的總和，即我們已經給數組大小N，使得n < = 100000，數組將有正面和負面的整數，現在我們必須找到數組的最大子集的總和，或者更正式地，我們必須找到索引i和j，使得這些元素之間的元素的總和最大。

下面是一個例子： N = 5，array = {12，-4，-10，4，9}，答案= 13，因爲4 + 9是我們能得到的最好的。

我知道，這可以通過在二次暴力破解的時間來解決，但我不知道這是否可以在線解決，對數時間。

在此先感謝。

Answer 1

根據this介紹，該算法通過Kadane顯然產生結合的線性運行時;從那裏取得的C++實現如下所示。

int maxSubArraySum(int a[], int size) 
{ 
    int max_so_far = INT_MIN, 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; 
    } 
    return max_so_far; 
}