一、题目描述：
给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5 , -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据
[要求]
1、 时间复杂度为O(n)，
2、空间复杂度为O(1)
示例：
输入：[1, -2, 3, 5, -2, 6, -1]
返回值：12
二、解题思路：
1、定义一个dp大小为n的数组，其中dp[i]的值代表到第i位的时候，以arr[i]结尾的连续子数组最大累加和。
2、当i =0时，dp[i] = arr[0]
3、当i != 0时， dp[i] = max(0,dp[i-1]) + arr[i](若 dp[i-1] <= 0即为负数时时dp[i-1] + arr[i]还不如arr[i]的本身大，所以当dp[i-1] <= 0时，dp[i-1] = arr[i], 当dn[i-1] >0时,dp[i] = dp[i-1] + arr[i])
4、最后返回值为dp数组中最大的值
三、解题代码：
class Solution:
def maxsumofSubarray(self , arr ):
# write code here
dp = [0] * len(arr)#开辟dp
res = arr[0]#保存最终的结果
dp[0] = arr[0]#初始化
for i in range(1,len(arr)):
dp[i] = max(dp[i-1],0) + arr[i]#维护dp[i]
res = max(res,dp[i])#每更新一个dp值就更新一下res
return res
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99771.html
