題目

給定一個(gè)非空整數(shù)列表 nums ，找到一個(gè)具有最大和的連續(xù)子列表（子列表最少包含一個(gè)元素），返回其最大和。

例如：

給定一個(gè)列表：[-2, 1, -3, 4, -1, 2, 1, -5, 4]，返回結(jié)果：6

給定一個(gè)列表：[-1]，返回結(jié)果：-1

實(shí)現(xiàn)思路1

• 直接暴力破解，但是需進(jìn)行2層遍歷
• 第一層遍歷設(shè)置當(dāng)前子列表的起始位置 i，第二層遍歷設(shè)置當(dāng)前連續(xù)子列表的結(jié)束位置 j
• 每次遍歷時(shí)尋找出遍歷到當(dāng)前位置的最大子序和 res

代碼實(shí)現(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

實(shí)現(xiàn)思路2

• 只進(jìn)行一層遍歷，需設(shè)置 res 表示遍歷到當(dāng)前位置的最大子序和，sum表示當(dāng)前連續(xù)子列表的元素之和
• 遍歷時(shí)候，如果sum小于0，那么針對后面計(jì)算 sum + i < 0 + i，所以就可以把前面元素都丟掉，即sum=0，然后從下一元素開始重新計(jì)算sum

代碼實(shí)現(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ù)更新中……）