XuLaLa.Tech

题目描述

请编写一个 Python 函数 max_subarray(nums)，接受一个整数列表 nums，返回该列表中和最大的连续子数组的和。

函数定义

def max_subarray(nums: List[int]) -> int:
"""
寻找最大子数组和
Args:
nums: 整数列表
Returns:
最大子数组和
"""
pass

输入

输入一个整数列表 nums，其中 $1 \leq |nums| \leq 10^5$。

输出

返回一个整数，为输入列表中和最大的连续子数组的和。

示例

>>> max_subarray([-2,1,-3,4,-1,2,1,-5,4])
6
>>> max_subarray([1])
1
>>> max_subarray([5, 4, -1, 7, 8])
23

提示

• 可以使用动态规划算法来解决本题，时间复杂度为 $O(n)$。
• 动态规划的状态转移方程为：$f(i) = max(nums[i], f(i-1) + nums[i])$，其中 $f(i)$ 表示以第 $i$ 个元素结尾的子数组的和最大值。
• 需要注意 Python 中列表是可变对象的特性，需要避免在循环中修改列表导致错误的情况。

完整代码

from typing import List
def max_subarray(nums: List[int]) -> int:
"""
寻找最大子数组和
Args:
nums: 整数列表
Returns:
最大子数组和
"""
if not nums:
return 0
max_sum = nums[0]
cur_sum = nums[0]
for i in range(1, len(nums)):
cur_sum = max(nums[i], cur_sum + nums[i])
max_sum = max(max_sum, cur_sum)
return max_sum
print(max_subarray([1]))