Python中的最大子数组

假设我们有一个整数数组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))

输入值

nums = [-2,1,-3,7,-2,2,1,-5,4]

输出结果

8