连续子数组的最大和
题目描述
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)O(n)。
例如，输入的数组为 {1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和为 18.
思路解析
- 思路1 遍历所有子数组
- 思路2 动态规划
F（i）：以arr[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
F（i）=max(F（i-1）+arr[i] , arr[i])代码
代码1 暴力求解
arr = [1, -2, 3, 10, -4, 7, 2, -5]# 暴力求解
maxsum = 0
for i in range(len(arr)):
cursum = 0
for j in range(i, len(arr)):
cursum += arr[j]
if cursum > maxsum:
maxsum = cursum
print(maxsum)代码2 动态规划 针对这个问题，递推公式是DP[i] = max{DP[i-1] + A[i],A[i]}；既然转移方程出来了，意味着写一层循环就可以解决这个问题。
# 动态规划 1
cursum, maxsum = 0, 0
for i in range(len(arr)):
if arr[i] > arr[i] + cursum: # 此时cursum<0
cursum = arr[i]
else:
cursum = arr[i] + cursum
if cursum > maxsum:
maxsum = cursum
print(maxsum)
# 动态规划 2
cursum, maxsum = 0, 0
for i in range(len(arr)):
cursum += arr[i]
if cursum > maxsum:
maxsum = cursum
if cursum < 0:
cursum = 0
print(maxsum)
# 动态规划 3
cursum, maxsum = 0, 0
for i in range(len(arr)):
cursum = max(arr[i], arr[i] + cursum)
maxsum = max(maxsum, cursum)
print(maxsum)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.02.21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录