欢迎光临CoolGeek
如有问题请留言评论

Python每日一题|最大子数组和

题目描述

请编写一个 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]))
赞(2) 打赏
如需转载请注明出处:CoolGeek » Python每日一题|最大子数组和
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址