求子数组之和的最大值

编程之美上的一道题,今天在别的地方看别人用贪心写的,真心觉得不对,所以做了一下。

一个有N个元素的一维数组(a[0], a[1]….a[n-1]),我们定义连续的a[i] ~ a[j],0<= i, j <=n-1为子数组。

显然这个数组中包含很多子数组,请求最大的子数组之和。

如果不想时间复杂度,用遍历所有可能子数组,然后找出最大值就可以了。

现在如果要求时间复杂度最小,那么肯定是要DP解的。

我们假设定义两个数组:

all[i]:表示从i~n-1,最大的子数组之和。

start[i]:表示包含i,并且从i~n-1,最大子数组之和。

all[i]中max只有三种可能:

(1) a[i]单独就是最大,之后再加一个就会变小。
(2)a[i]+…a[j]最大,即start[i]最大
(3)a[x]+..a[j]最大,即不包含i的后序某一个子数组和最大。

最终,最大的子数组之和是all[0]。根据上述3个可能,很容易写出如下递推式:

start[i] = max (a[i], a[i]+start[i+1])
all[i] = max(start[i], all[i+1])

注意我们把上面max(a, b, c)拆成了两个max(a, b)

由于我们在计算start[i]/all[i]时候需要start[i+?]的值,所以我们从后向前递推dp。

代码如下,时间复杂度O(n):

 

 

Leave a Reply

Your email address will not be published.