劍指 Offer 42. 連續子數組的最大和

話不多說，先上題目

輸入一個整型數組，數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。

要求時間複雜度為O(n)。

示例1:

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

 ​

法一

暴力解法：窮舉

法二

動态規劃

據說是動态規劃的最簡單的題了，在此學習記錄一下

END

作者：金木研King