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