求最大和的子数组

题目简介：

输入一个整形数组，里有正也负。
数组中连续的一个或多整成子数组，每都有一个和。
求所有子数组的和最大值。要时间复杂度为 O(n)。

例如输入的数组为 1, -20, 3, 10, -40, 2, 20, -5，和最大 的子数组为2, 20，因此输出为该子数组的和 22 。

题目解答：

1. 先判断sum>max，修正max;

2. 当sum<0时，sum置0；

3. 为了输出最大和的子数组（不考虑存在多个子数组都为最大和，这种情况只输出第一个出现的子数组），我们定义连个变量left和right。right获取比较简单，当max值发生变化时，right=i。left为最近一次sum<0时的i+1。

完整代码（测试平台：www.anycodex.com）：

#include<stdio.h>

int howmany (int *p,int len)  
{  
	int i=0;
	int sum = 0;
	int max = *p;
	int left = 0;
	int right = 0;
	int tmp = 0;
	for (; i < len; i++)
	{
		sum += *(p + i);
		if(sum > max)
		{
			max = sum;
			right = i;
			left = tmp + 1;		
		}	
		if (sum < 0)
		{	
			sum = 0;
			tmp = i;
		}				
	}
	printf("The max sequence is: \n");
	for (int j = left; j <= right; j++)
	{
		printf(" %d ", *(p + j));
	}
	printf("\n");
	return max;
}  

int main()
{    
	int a[]={ 1, -20, 3, 10, -40, 2, 20, -5};
	int len = sizeof(a)/sizeof(int);
	printf("The max sum is %d\n",howmany((int *)a,len));
}

求最大和的子数组

原文：http://blog.csdn.net/xiaxia__/article/details/19284837