求连续的子数组的和

                                                                               求连续的子数组的和

                                                                               郭志伟&王扣柱

算法一：

具体思路：

1.创建一个数组，首先在主函数里判断是否全为负数，若全部是负数则直接选出最大值即可，否则调用addMax（int n,int*a)函数

2.在addMax函数里首先设置max=0，再设置一个中间值median=0；

3.for循环从数组的第一个数开始加起median=median+a[i];如果值为负就舍去，在下次循环时从新给median赋值一个新的数值，如果和大于0则与max比较，若大于max就max=median,否则继续循环重复上述步骤直到循环结束

代码如下：

#include<iostream>
using namespace std;
int addMax(int n,int*a)
{
	int i,max=0,median=0;
	for(i=0;i<n;i++)
	{
		if(median<0)
			median=a[i];
		else
			median=median+a[i];
		if(max<median)
			max=median;
	}
	return max;
}
int main()
{
	int a[7]={-1,-4,5,-6,9,8,-1};
	int i,m=0,max=0;
	for(i=0;i<7;i++)//判断是否全为负数
	{
		if(a[i]<0)
			m++;
	}
	if(m=7)
	{
		max=a[0];
		for(i=1;i<7;i++)
		{
			if(max<a[i])
				max=a[i];
		}
	}
	else
	{
		max=addMax(7,a);
	}
	cout<<max<<endl;
	return 0;
}

算法二：

具体思路：

1.创建一个数组，首先在主函数里判断是否全为负数，若全部是负数则直接选出最大值即可，否则调用函数进行具体运算

2.两两合并，即正数与正数合并，负数与负数合并，若两头中任意一头有负数，则先排除它，最终变味+-+-+-+...+-+形式

3.从开头取三个数必为+-+形式，求和，如果和大于三个数之中任意一个正数则合并它们，否则取下一组三个数+-+并按刚才方法进行比较

4.通过多次比较来缩减范围，最后形成+-+三个数来做最终比较，然后输出

5.例：1 -2 -3 5 -1 4 3 -2 7

         1 -5 5 -1 7 -2 7

         1 -5 11 -2 7

         1 -5 16

结果：max=16

注：此算法的代码实现略复杂，在此暂不做讲述，日后有机会再实现它