题目描述
题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 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)
