可能重複：
Maximum Contiguous Subsequence Sum of At Least Length L算法分析 - 任何想法？
設X = {X1，X2，...，XN}是任意數（正或負）的序列。給出一個O（n）時間算法來找出連續元素xi，xi + 1，...，xj的子序列，其和在所有連續子序列中是最大的。例如，對於X = {2,5，-10,3,12，-2,10，-7,5}，{3,12，-2,10}是一個解決方案。
這個問題可以使用動態規劃來解決。 假設你的輸入是數組a，你可以創建一個長度相同的數組S。 以下是問題的遞歸關係。
S[i] = S[i-1] + a[i] > a[i] ? S[i-1] + a[i] : a[i]
基本情況：S[0] = a[0]
保持一個max跟蹤最大總和。最後返回max。
答案是http://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm
這個算法背後的想法是，我們假設我們知道問題的長度爲N的數組的真正最大的子陣列，而且我們知道這開始於兩端的最大子數組。 （基本原理：如果我們假設我們知道碰到兩端的最大序列，並且我們逐漸將更多元素粘合到最後，那麼我們不能錯過真正的最大子陣列，因爲在某個點添加到末尾的元素將是相同的元素作爲真正的最大子陣列的終點）。加上一個額外的元素可能會增加附加到最後的最長子陣列的長度。如果子陣列的總和低於0，我們重置它。如果它超出了我們當前最佳候選解決方案的真正最大子陣列，我們將取代我們最好的候選解決方案。
或者，我們可以使用集成的力量。 （這是一個你可以免費做的O（N）過程;也可以免費區分）。然後我們看所有的極值，搜索兩個極值MIN和MAX，使得MAX在MIN的右邊（或否則你會找到最負的總和），並且還使MAX-MIN（連續和）最大。你可以強制這個子問題（如果極限數小於sqrt（N），它仍然是O（N）），或者你可以用更有效的方式解決它[可以在這裏使用一些幫助]。
如果是這樣，請將作業問題標記爲「家庭作業」;提及迄今爲止你如何解決這個問題也可以提供幫助。如果不做功課，請忽略。 – ninjagecko
@ninjagecko：[家庭作業標籤現已正式棄用]（http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially- depprecated）。 –
@JerryCoffin：啊，很高興知道！ – ninjagecko