連續子數組的最大和（基于動态規劃）

　　輸入一個整型數組，數組裡有正數也有負數。數組中一個或連續的多個整數組成一個子數組。求所有子數組的和的最大值。要求時間複雜度為O(n)。例如輸入的數組為{1,-2,3,10,-4,7,2,-5}，和最大的子數組為{3,10,-4,7,2}，是以輸出為該子數組的和18。

一般解法

從頭到尾累加數字，儲存到一個臨時變量curr_sum中

如果前幾項的和為負，則加上此和之後比本身的值還要小，抛棄原來所計算得到的和，curr_sum從本元素開始計數 ；否則，把目前元素累加到curr_sum

把curr_sum與最大值max_sum比較（max_sum儲存每個連續數組的最大和）

 動态規劃

　　f(i)表示以第i個數字結尾的子數組的最大和，那麼隻需求出max[f(i)],狀态轉移方程如下

code：