问题描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

解题思路

设置数组 d，其第 i 个分量表示所有以 i 为结束索引的连续子数组的和中的最大值。

则：

• 如果 d[i] > 0，那么 d[i + 1] = d[i] + nums[i + 1]
• 否则，d[i + 1] = nums[i + 1]

数组 d 中的最大值就是要求的最大和。

Python 实现

xxxxxxxxxx
def max_sub_array(nums):
    m = None
    s = 0
​
    for num in nums:
        if s > 0:
            s = s + num
        else:
            s = num
        if m is None or s > m:
            m = s
​
    return m
​
​
if __name__ == "__main__":
    print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)
​