数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚
法学Python 中的最大子数组
假设我们有一个整数数组 A。我们必须找出长度至少为 1 的连续子数组，并且其和最大，并返回其和。因此，如果数组 A 类似于 A = [-2,1,-3,4,-1,2,1,-5,4]，则总和为 6。子数组将为 [4, -1, 2, 1]
为了解决这个问题，我们将尝试使用动态规划方法。
- 定义一个数组 dp 与 A 的大小相同，并将其填充为 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
更新于：28-4-2020
4K+ 浏览
广告