CWYAlpha

Just another WordPress.com site

Thought this was cool: 求子数组之和的最大值

leave a comment »


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

一个有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;
}

 

 
from 四号程序员四号程序员: http://www.coder4.com/archives/3198

Written by cwyalpha

五月 23, 2012 在 6:38 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: