python算法每日一练:连续子数组的最大和

2024-01-09 10:12:33

这是一道关于动态规划的算法题:

题目描述:
给定一个整数数组 nums,请找出该数组中连续子数组的最大和,并返回这个最大和。

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

编写一个函数 maxSubArray(nums) 来解决这个问题,函数的输入参数 nums 是一个整数数组,返回值为最大和。

要求使用动态规划的思想来解决这个问题。

提示:

  • 可以假设输入的数组至少包含一个元素。

请尝试解答这道题,如果有任何疑问,请随时提问。

def maxSubArray(nums):
    n =len(nums)
    dp = n * [0]
    dp[0] = nums[0]
    max_sum = dp[0]
    for i in range(1,n):
        dp[i] = max(dp[i-1]+nums[i],nums[i])
        max_sum = max(max_sum,dp[i])
    print(max_sum)
nums=[-2, 1, -3, 4, -1, 2, 1, -5, 4]
maxSubArray(nums)

dp[i-1] 的含义。在遍历数组 nums 的过程中,我们计算 dp[i] 的值,表示以 nums[i] 结尾的连续子数组的最大和。在计算 dp[i] 时,我们需要考虑两种情况:

nums[i] 单独构成一个子数组,此时 dp[i] = nums[i]。
将 nums[i] 与前面的连续子数组相连,此时 dp[i] = dp[i-1] + nums[i]。
我们需要选择使 dp[i] 达到最大的方式,因此我们比较这两种情况的结果,取较大的值作为 dp[i] 的值。

通过这种方式,我们不断更新 dp 数组的值,最终得到以每个位置 i 结尾的连续子数组的最大和。遍历完整个数组后,最大的 dp[i] 值即为所求的最大和。

文章来源:https://blog.csdn.net/qq_42476938/article/details/135415472
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。