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

一个有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)：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b)
{
	if(a>b)
	{
		return a;
	}else
	{
		return b;
	}
}

int max_sum(int* arr, int n)
{
	// Helper array
	int i;
	int* start = (int*)malloc(sizeof(int)*n);
	int* all = (int*)malloc(sizeof(int)*n);
	int final;
	if(!start || !all)
	{
		return -1;
	}
	memset(start, 0, sizeof(int)*n);
	memset(all, 0, sizeof(int)*n);
	// dp
	start[n-1] = arr[n-1];
	all[n-1] = arr[n-1];
	for(i=n-2;i>=0;i--)
	{
		start[i] = max(arr[i], arr[i]+start[i+1]); 
		all[i] = max(start[i], all[i+1]); 
	}
	final = all[0];
	// Free helper array
	free(start);
	free(all);
	return final;
}

int main()
{
	//int arr[6] = {1, -2, 3, 5, -3, 2}; // 8
	int arr[6] = {0, -2, 3, 5, -1, 2}; // 9
	//int arr[5] = {-9, -2, -3, -5, -3}; // -2
	printf("max sum of sub_arr: %d \n", max_sum(arr, sizeof(arr)/sizeof(int)));
	return 0;
}