（三） 求子数组的最大和

题目：求子数组的最大和
输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为 O(n) 。
例如输入的数组为 1, -2, 3, 10, -4, 7, 2, -5 ，和最大的子数组为 3, 10, -4, 7, 2 ，因此输出为该子数组的和18 。

分析：

如果第一次遇见这样的题目，在时间复杂度为O(n)的条件下，似乎不能做到。而最容易想到的就是穷举法了，元素个数为1的子数组有n个，元素个数为2的子数组有n-1，……这样下去，明显不符合时间复杂度O(n)的要求。该怎么办呢？贪心算法！以上面的数组为例，首先初始化子数组和的最大值max为0，数组元素和sum为0，从第一个元素开始计算，若相加后的sum为正，且sum>max，则max=sum，若sum<0，则sum=0，依次计算下去，……

然而这样会有一种特殊情况，即数组的全部元素均为负数，此时最后的max=0，不是子数组和的最大值（应该为数组元素中值最大的一个负数）。解决该特殊情况最容易想到的方法就是重新循环一次数组（不好，又循环了一次），找出最大值，或者在第一次循环时顺便找出最大值，此种情况的代码如下（其实，还有一种更巧妙的方法，到下面再说）：

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

bool maxSubarray(int data[], int size,int &max)
{
if (size<=0)
{
printf("error array size\n");
return false;
}
int sum = 0, maxElement=-(1<<31);
max=0;
for(int i=0;i<size;i++)
{
if(data[i]>maxElement)
maxElement=data[i];

sum +=data[i];
if(sum>max)
{
max=sum;
}
else if(sum<0)
{
sum=0;
}
}

if(max==0)//all negative elements
max=maxElement;

return true;

}

int main()
{
int data[]={1, -2, 3, 10, -4, 7, 2, -5};
int max;
if( maxSubarray(data,8,max))
printf("%d\n",max);

int data2[]={-1, -2, -3, -10, -4, -7, -2, -5};
if( maxSubarray(data2,8,max) )
printf("%d\n",max);

getchar();
return 0;
}

另一种解决特殊情况的巧妙方法在于max初始值的设置，我们可以通过赋初值max==-(1<<31)；就可以很轻松的搞定特殊情况了。因为此时即使数组元素都为负，那么其中的元素也一定大于等于max，所以就避免了上面所述的特殊情况。代码如下：

bool maxSubarray(int data[], int size,int &max)
{
if (size<=0)
{
printf("error array size\n");
return false;
}
int sum = 0;

max=-(1<<31);
for(int i=0;i<size;i++)
{

sum +=data[i];
if(sum>max)
{
max=sum;
}
else if(sum<0)
{
sum=0;
}
}
return true;
}

可见，代码简约了不少^_^

另外，类似的问题还有：有一个数组a[n],里面的数只有两种：-1或1。i，j是两个整数，假设0<=i<=j<=n-1，找出a[i]到a[j]中连续数之和最大的部分（如果最大部分存在相等的则优先找最短的）。问题的解法是类似的，至于寻找最短的也比较简单，就不多说了