查找數組中元素的最大和

編寫一個程序，該程序通過給定的整數值數組（包含負整數）查找數組中連續元素的最大總和。查找數組中元素的最大和

實施例：

2，3，-6，-1，2，-1，6,4，-8,8

給出

我在尋找一種解決方案，它是固定r比O（N^2）。

來源

2012-09-09 user1106337

1,2,5,6不連續。如果您對可以採取的子集沒有限制，這是Subset-Sum問題，它是NP-Complete，但我不認爲是這種情況。 – amit

對不起，誤會。在描述和示例中，我犯了一個錯誤。 :)我已經更新了兩個。 – user1106337

線性掃描可以解決這個問題。總結並與當前最大值進行比較，如果總和<0，則將總和重置爲0並繼續。這種貪婪的解決方案已被證明是正確的。這就是所謂的卡丹的算法：http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh

我覺得Kadane's Algorithm是你想要

來源

2012-09-09 13:12:08 Qyrus

鏈接不再有效 – fayyazkl

什麼這實際上是一本教科書的問題，我在大學學習（數據結構與算法由馬克·艾倫·韋斯C）...這是一個非常美麗和優雅的解決方案，解決了在O（N）

int MaxSubsequenceSum(int A[]) 
{ 
    int sum = 0, maxSum = 0; 

    for (int j = 0; j < A.Length; j++) 
    { 
     sum = sum + A[j]; 

     if (sum > maxSum) 
      maxSum = sum ; 
     else if (sum < 0) 
      sum = 0; 
    } 
    return maxSum; 
}

來源

2012-09-09 14:08:08

您的文章由匿名用戶編輯，然後獲得批准。你能證實這些變化實際上是正面的嗎？它似乎顯着改變了邏輯。 – Gray

不，我沒有批准它，也沒有顯着改善答案。我認爲這是完成點 –

由匿名用戶完成，所以沒有代表獎勵。隨時回滾。他們[留下了評論]（http://stackoverflow.com/posts/12339772/revisions）瞭解他們爲什麼這麼做。 – Gray

-1

可以首先給定的陣列中的降序進行排序，然後通過總結陣列的前三個元素：由intializing的sum=0和打印總和 sum=arr[0]+arr[1]+arr[2] 。

來源

2014-06-12 20:14:35 bitsk

查找數組中元素的最大和

回答

相關問題