題目描述
給定一個整數(shù)數(shù)組 nums 甸祭，找到一個具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個元素）腾节，返回其最大和林艘。
示例
示例 1：
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大堪滨，為 6计螺。
解答方法
方法一：動態(tài)規(guī)劃
思路
首先，對于數(shù)組中的第i個數(shù)冶忱，它的狀態(tài)有兩種：(a)nums[i] 在最大子序中尾菇；(b)nums[i]不在最大子序中。
dp[i]表示nums中以nums[i]結(jié)尾的最大子序和,在分析第i個數(shù)時囚枪，前i-1個數(shù)已經(jīng)達到最優(yōu)解派诬，最優(yōu)解時，用dp[i-1]表示第i-1個數(shù)的狀態(tài)链沼。
res為dp中最大的數(shù)
代碼
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
res = dp[0]
for i in range(1,len(nums)):
dp[i] = max(nums[i],dp[i-1]+nums[i])
res = max(res, dp[i])
return res
時間復(fù)雜度
O(n)
空間復(fù)雜度
方法二：貪心
思路
從左往右遍歷默赂，一個個數(shù)字加過去，如果sum<0,重新開始找子序串
代碼
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
sum = 0
for num in nums:
sum += num
res = max(res, sum)
if sum < 0:
sum = 0
return res
時間復(fù)雜度
O(n)
空間復(fù)雜度
O(1)
