題目
給定一個非空整數(shù)列表 nums ，找到一個具有最大和的連續(xù)子列表（子列表最少包含一個元素），返回其最大和。
例如：
給定一個列表：[-2, 1, -3, 4, -1, 2, 1, -5, 4]怖喻，返回結(jié)果：6
給定一個列表：[-1]，返回結(jié)果：-1
實現(xiàn)思路1
- 直接暴力破解岁诉，但是需進行2層遍歷
- 第一層遍歷設(shè)置當(dāng)前子列表的起始位置 i锚沸，第二層遍歷設(shè)置當(dāng)前連續(xù)子列表的結(jié)束位置 j
- 每次遍歷時尋找出遍歷到當(dāng)前位置的最大子序和 res
代碼實現(xiàn)
def maxSubArray(nums):
res = nums[0]
for i in range(len(nums)):
sum = 0
for j in range(i, len(nums)):
sum += nums[j]
res = sum if res < sum else res
return res
實現(xiàn)思路2
- 只進行一層遍歷，需設(shè)置 res 表示遍歷到當(dāng)前位置的最大子序和涕癣，sum表示當(dāng)前連續(xù)子列表的元素之和
- 遍歷時候哗蜈，如果sum小于0，那么針對后面計算 sum + i < 0 + i，所以就可以把前面元素都丟掉恬叹，即sum=0扳躬，然后從下一元素開始重新計算sum
代碼實現(xiàn)
def maxSubArray(nums):
res, sum = nums[0], 0
for i in nums:
sum += i
res = sum if res < sum else res
sum = 0 if sum < 0 else sum
return res
更多Python編程題执赡，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
