2012-09-09 45 views
5

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

實施例:

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

給出

我在尋找一種解決方案,它是固定r比O(N^2)。

+0

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

+0

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

+1

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

回答

4

什麼這實際上是一本教科書的問題,我在大學學習(數據結構與算法由馬克·艾倫·韋斯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; 
} 
+0

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

+0

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

+0

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

-1

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

相關問題