Python 中的最大子数组

pythonserver side programmingprogramming更新于 2025/10/31 18:52:17

假设我们有一个整数数组 A。我们必须找到长度至少为 1 且总和最大的连续子数组，并返回其总和。因此，如果数组 A 为 A = [-2,1,-3,4,-1,2,1,-5,4]，则总和为 6。子数组为 [4, -1, 2, 1]

为了解决这个问题，我们将尝试使用动态规划方法。

定义一个与 A 大小相同的数组 dp，并用 0 填充它
dp[0] := A[0]
对于 i = 1 到 A 的大小 – 1
- dp[i] := dp[i – 1] + A[i] 和 A[i] 的最大值
返回 dp 中的最大值

让我们看下面的实现，以便更好地理解 −

示例 (Python)

class Solution(object):
   def maxSubArray(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      dp = [0 for i in range(len(nums))]
      dp[0] = nums[0]
      for i in range(1,len(nums)):
         dp[i] = max(dp[i-1]+nums[i],nums[i])
      #print(dp)
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.maxSubArray(nums))