Maximum subarray_problem understanding

我正在研究最大的子數組問題。看來我沒有得到核心思想。假設你有以下數組：int arr[] ={10, 4, 2, 12, 16, 1}根據我所理解的最大子數組應該等於14，因爲最低和最高可能的子數組是2（第三個元素）和16（第五個元素）對嗎？那麼，顯然不是。我實現了線性時間算法，我發現這裏：http://heliang.me/wiki/index.php?title=4.1_The_maximum-subarray_problem 它的實現在C++中」Maximum subarray_problem understanding

int max_sarr(int arr[], int size) 
{ 
    int max_sum = -9999; 
    int sum = 0; 
    for(int i = 0; i < size; i++) 
    { 
     sum += arr[i]; 
     if(sum > max_sum) 
      max_sum = sum; 
     if(sum < 0) 
      sum = 0; 
    } 
    return sum; 
} 
int main() 
{ 
    int arr[] = {10, 4, 2, 12, 16, 1}; 
    int p = max_sarr(arr, 6); 
    cout << p << endl; 
    return 0; 
}

輸出是45所以...這裏是我的思維過程的錯誤

來源

2013-04-21 Bloodcount

最大的子陣列只是一個最大可能總和的子陣列，就這麼簡單。 – 2013-04-21 13:18:59

你的理解是最錯誤和奇怪的。該算法是正確的。很難找到你的錯誤，因爲你沒有展示任何思維過程。 – 2013-04-21 13:25:37

你誤會了問題是找到給定數組的連續子數組，使得它具有所有子數組中最高的總和，也就是說，它基本上找到數組中的第一個元素和最後一個元素，如果總結了包含和在它們之間，會給你最大的可能值。

如果數組中的所有值都是正數，則最大子數組始終是整個數組。在這種情況下，如果將數組中的所有元素相加，則得到45.

考慮一個值爲{-5, 10, -3, 22}的數組。我們可以枚舉所有的這種子陣列：

Subarrays of length 0: {} 
Subarrays of length 1: {-5}    {10}   {-3}  {22} 
Subarrays of length 2: {-5, 10}   {10, -3}  {-3, 22} 
Subarrays of length 3: {-5, 10, -3}  {10, -3, 22} 
Subarrays of length 4: {-5, 10, -3, 22}

與最大總和子陣列{10 -3 22}，其總和爲29

來源

2013-04-21 13:19:52

sftrabbit的答案是偉大的，但我強烈建議的最大子數列問題部分CLRS book第68頁。它非常清楚，並且還討論了問題的漸近複雜性和真實生活發生率。

除此之外，正如您所期望的那樣，包含所有正元素的數組，其最大子數組將是數組本身。

來源

2013-04-21 13:32:12

Maximum subarray_problem understanding

回答

相關問題