x元素的最大連續子序列總和

因此，我想出了一個問題，我已經查找和搜索，但沒有找到答案...什麼是最好的（並說最好的，我的意思是最快）的方式來獲得x元素的最大連續子序列總和？假設我已經：A [] = {2,4,1,10,40,50,22，1,24,12,40,11，...}。然後我問：x元素的最大連續子序列總和

"What is the maximum contigous subsequence on array A with 3 elements?"

請一個陣列，使超過10萬組的元素想象這...有人能幫助我嗎？

謝謝你的時間和你的幫助！

來源

2015-08-08 Fábio Colaço

我Google了一下，發現this：

使用分而治之的辦法，我們可以發現在O（nLogn）時間的最大子數組之和。以下是除法和征服算法。

該問題的Kadane算法需要O（n）次。因此，Kadane的算法比分而治之的辦法

更好地看到the code：

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
      max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
return max_so_far

來源

2015-08-08 04:39:37

這是不是真的我在尋找什麼，因爲我需要用X元素分組的最高金額...想象一下，在我上面的例子中，最大總和就是所有元素，因爲它們都是正數，但我想要最大的總和由3個元素組成......所以：這將是40 50 22。 –

x元素的最大連續子序列總和

回答

相關問題