HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。給一個數組，傳回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)
時間限制： C/C++ 1秒，其他語言2秒 空間限制： C/C++32M，其他語言64M
背景知識介紹
在做題前，首先給大家介紹一種非常典型的算法——動态規劃算法。在維基百科中，動态規劃算法是這樣解釋的：動态規劃（英語：Dynamic programming，簡稱DP）是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動态規劃常常适用于有重疊子問題和最優子結構性質的問題，動态規劃方法所耗時間往往遠少于樸素解法。動态規劃背後的基本思想非常簡單。大緻上，若要解一個給定問題，我們需要解其不同部分（即子問題），再根據子問題的解以得出原問題的解。通常許多子問題非常相似，為此動态規劃法試圖僅僅解決每個子問題一次，進而減少計算量：一旦某個給定子問題的解已經算出，則将其記憶化存儲，以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關于輸入的規模呈指數增長時特别有用。
動态規劃在查找有很多重疊子問題的情況的最優解時有效。它将問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算并被儲存，從簡單的問題直到整個問題都被解決。是以，動态規劃儲存遞歸時的結果，因而不會在解決同樣的問題時花費時間。動态規劃隻能應用于有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解（對有些問題這個要求并不能完全滿足，故有時需要引入一定的近似）。簡單地說，問題能夠分解成子問題來解決。
最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的，我們就稱該問題具有最優子結構性質（即滿足最優化原理）。最優子結構性質為動态規劃算法解決問題提供了重要線索。無後效性。即子問題的解一旦确定，就不再改變，不受在這之後、包含它的更大的問題的求解決策影響。子問題重疊性質。子問題重疊性質是指在用遞歸算法自頂向下對問題進行求解時，每次産生的子問題并不總是新問題，有些子問題會被重複計算多次。動态規劃算法正是利用了這種子問題的重疊性質，對每一個子問題隻計算一次，然後将其計算結果儲存在一個表格中，當再次需要計算已經計算過的子問題時，隻是在表格中簡單地檢視一下結果，進而獲得較高的效率。
具體實作一
本題是動态規劃算法的典型應用，根據上述對動态規劃的解釋，我們可以用函數f(i)表示以第i個數字結尾的子數組的最大和，那麼我們需要求出max[f(i)]，其中0 <= i <= n。我們可以用如下遞歸公式求f(i)：
f(i) = pData[i] i = 0或者f(i-1) <= 0
f(i) = f(i-1) + pData[i] i 不等于 0并且f(i-1) > 0
我們解釋一下這個遞歸公式所表示的含義：當以第I-1個數字結尾的子數組中所有數字的和小于0時，如果把這個負數與第i個數累加，則得到的結果比第i個數字本身還要小，是以這種情況下以第I個數字結尾的子數組就是第I個數字本身。如果以第I-1個數字結尾的子數組中所有數字的和大于0，則與第i個數字累加就得到以第i個數字結尾的子數組中所有數字的和。
不過需要我們注意的是通常我們用遞歸的方式分析動态規劃的問題，但最終都會基于循環去編碼。接下來我們用java将其實作。
代碼效果圖如圖所示：
我們加上Main()在本地IDE運作，檢視一下運作結果，具體實作如下：
代碼測試效果圖如下：
具體實作二
除了我們上述用動态規劃的思路做出來，其實這道題有很強的規律性，是以，我們可以通過舉例分析數組的規律來把此題做出來。具體的步驟如下：
從頭到尾逐個累加數組中的每個數字，初始化和為0；
定義兩個變量：“累加子數組和”和“最大子數組和”，第一步把數組中的第一個數字指派給他們，然後從第二個數字開始累加，累加值放入“累加子數組和”。
1.如果目前“累加子數組和”小于0，那抛棄前面的“累加子數組和”，從下一個數字開始重新累加，“最大子數組和”的值不更新。
2.如果目前“累加子數組和”大于0，再讓目前“累加子數組和”和目前的“最大子數組和”進行比較。
如果目前“累加子數組和”大于目前“最大子數組和”，則更新“最大子數組和”的值為“累加子數組和”的值。
如果目前“累加子數組和”小于目前“最大子數組和”，“最大子數組和”的值不更新。
3.再加入數組中的下一個值，“累加子數組和”進入下一輪的累加，“最大子數組和”也進入下一輪的更新。知道數組中所有值都累加完畢。
這樣進行一次累加的周遊之後，就可以得到最終的最大累加和，時間複雜度是O(n)。根據以上的思路，我們可以進行一次示範，例如{1， -2， 3， 10， -4， 7， 2， -5}。具體過程如下：
我們分别用java和python實作如下，不過java是從前往後周遊，而python是從後往前周遊，結果是一緻的：
根據測試代碼運作結果可知和我們之前與練習尋找最大子數組的結果是一緻的。接下來我們利用python将其思路按照從後往前進行周遊，實作代碼如下：
本道題主要是通過數組考察動态規劃思想，動态規劃思想在資料結構與算法中也是特别的重要的，是以在做本題之前，我們首先給大家介紹了動态規劃算法的基礎知識，接下來通過一個遞歸式将其實作，不過盡管是遞歸，但是在實際寫代碼時候，還是将遞歸轉換為疊代，這樣大大減少了時間複雜度，大大提高了運作速度。并且我們還從舉例找規律的角度出發來完成該題，通過找規律，并且舉例子按照給定的思路走了一遍，并且分别用java和python将其實作。通過測試代碼發現和我們舉例子走的結果完全符合。是以，我們在做題的時候，應該多次嘗試各種方法，擴充自己的思維，寫出優質的代碼。總之，我們要繼續加油，争取早日找到工作，Good Luck！！！
[1] kongmin_123
[2] CC‘s World
[3] 動态規劃算法