劍指 Offer 42. 連續(xù)子數(shù)組的最大和

輸入一個(gè)整型數(shù)組，數(shù)組中的一個(gè)或連續(xù)多個(gè)整數(shù)組成一個(gè)子數(shù)組。求所有子數(shù)組的和的最大值。

要求時(shí)間復(fù)雜度為O(n)。

?

示例1:

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

輸出: 6

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

?

然后返回dp中的最大值即所求最大值。

我不太喜歡直接改原數(shù)組，所以另外開(kāi)了個(gè)。

class?Solution:

????def?maxSubArray(self,?nums:?List[int])?->?int:

????????lenNums=len(nums)

????????dp=[0]*lenNums

????????dp[0]=nums[0]

????????for?i?in?range(1,lenNums):

????????????if?dp[i-1]>0:

????????????????dp[i]=dp[i-1]+nums[i]

????????????else:

????????????????dp[i]=nums[i]

????????return?max(dp)

另外一種dp思路：

居然下面那個(gè)更快，我有點(diǎn)不太理解。。