动态规划系列(5)——连续子数组的最大和

xiaoxiao2021-03-01  9

题目:输入一个整型数组,数组中有整数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

解析:令f(i)代表以第i个数字结尾的子数组的最大和,那么我们可以求出所有的最大和,然后求max(f[i])。如果上一个数之前的子数组和小于0,则到当前的数的子数组的和为当前数的大小;如果上一个数之前的子数组和大于0,则到当前的数的子数组的和为当前数的大小加上一子数组的和。递归公式如下:

 

代码如下:

# -----------动态规划------------- def FindGreatestSumOfSubArray_dp(arr): global g_InvalidInput if arr == None or len(arr) <= 0: g_InvalidInput = True return 0 g_InvalidInput = True opt = [0] * len(arr) opt[0] = arr[0] for i in range(1, len(arr)): if opt[i-1] <= 0: opt[i] = arr[i] else: opt[i] = arr[i] + opt[i-1] return max(opt)

 

转载请注明原文地址: https://www.6miu.com/read-3350176.html

最新回复(0)