看到這個題目，我們首先想到的是求出這個整型數組所有連續子數組的和，長度為n的數組一共有 n(n+2)/2個子數組，是以要求出這些連續子數組的和最快也需要O(n^2)的時間複雜度。但是題目要求的O(n)的時間複雜度，是以上述思路不能解決問題。
看到O(n)時間複雜度，我們就應該能夠想到我們隻能對整個數組進行一次掃描，在掃描過程中求出最大連續子序列和以及子序列的起點和終點位置。假如輸入數組為{1,-2,3,10,-4,7,2,-5}，我們嘗試從頭到尾累加其中的正數，初始化和為0，第一步加上1，此時和為1，第二步加上-2，此時和為-1，第三步加上3，此時我們發現-1+3=2，最大和2反而比3一個單獨的整數小，這是因為3加上了一個負數，發現這個規律以後我們就重新作出累加條件：如果目前和為負數，那麼就放棄前面的累加和，從數組中的下一個數再開始計數。
代碼執行個體：
View Code
經過@Yu's 技術生涯 測試，發現我上面的代碼确實存在問題，現在做了如下修改：
1.添加了一個周遊用于儲存周遊數組中發現的最大和的起始，原來的start和end隻用于儲存真是的開始于結尾。
2.當currSum<0的時候，我們隻讓p值為最大和子數組的開始
3.在最後判斷currSum>greatestSum的時候，隻有當currSum>greatestSum成立，才讓start=p，否則就表明以p開頭的子數組最大和不是最大的。
示例代碼如下：
如果用函數f(i)表示以第i個數字結尾的子數組的最大和，那麼我們需要求出max(f[0...n])。我們可以給出如下遞歸公式求f(i)
這個公式的意義：
當以第(i-1)個數字為結尾的子數組中所有數字的和f(i-1)小于0時，如果把這個負數和第i個數相加，得到的結果反而不第i個數本身還要小，是以這種情況下最大子數組和是第i個數本身。
如果以第(i-1)個數字為結尾的子數組中所有數字的和f(i-1)大于0，與第i個數累加就得到了以第i個數結尾的子數組中所有數字的和。
其實上述兩種方法的實作方式非常相似，隻是解體思路不同而已。通常我們會使用遞歸的方式分析動态規劃的問題，但是最終都會基于循環去寫代碼。在動态規劃方法中建立了一個數組c[]用于存儲中間結果，而第一種方法中隻需要一個臨時變量currSum.
作者：xwdreamer