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

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

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

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

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

我们假设定义两个数组：

all[i]：表示从i~[......]

继续阅读