九度OJ 1077：最大序列和 （DP）

時間限制：1 秒

記憶體限制：32 兆

特殊判題：否

送出：5600

解決：1637

題目描述：

給出一個整數序列S，其中有N個數，定義其中一個非空連續子序列T中所有數的和為T的“序列和”。

對于S的所有非空連續子序列T，求最大的序列和。

變量條件：N為正整數，N≤1000000，結果序列和在範圍（-2^63,2^63-1）以内。

輸入：

第一行為一個正整數N，第二行為N個整數，表示序列中的數。

輸出：

輸入可能包括多組資料，對于每一組輸入資料，

僅輸出一個數，表示最大序列和。

樣例輸入：

5
1 5 -3 2 4

6
1 -2 3 4 -10 6

4
-3 -1 -2 -5      

樣例輸出：

9
7
-1      

來源：

2006年清華大學計算機研究所學生機試真題

思路：

應該算是最簡單的dp了吧。

從0到n-1，依次求最後一個數為第i個數序列中的最大序列和。

最後在這些序列和中求出最大值即可。

代碼：