题目描述
给定一个整数数组，找出一个连续子数组（包含至少一个元素），使其和最大，返回这个最大和。
示例
输入：nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
输出：6（子数组 [4, -1, 2, 1] 的和最大）
提示
使用 Kadane 算法：维护一个当前子数组和 current_sum 和一个最大和 max_sum。当 current_sum 变为负数时，重新开始计算。
参考答案
def max_sub_array(nums):
"""最大子数组和（Kadane 算法）"""
if not nums:
return 0
max_sum = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
# 如果当前和为负，不如从头开始
current_sum = max(nums[i], current_sum + nums[i])
# 更新最大和
max_sum = max(max_sum, current_sum)
return max_sum
# 测试
print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6
print(max_sub_array([1])) # 1
print(max_sub_array([5, 4, -1, 7, 8])) # 23
print(max_sub_array([-1])) # -1