算法4：求整型数组的连续子数组的最大和
输入一个整型数组，数组里既有正数也有负数，数组中连续一个或者多个组成整型子数组，每个子数组都有一个和，求所有子数组的最大和，要求时间复杂度为O(n)。
解题思路
使用贪婪算法，数组从开始往后遍历，记录最大和，当前和小于0时，当前子数组和置为0.
c++代码如下
//使用贪婪算法，遇到sum<0的情况，就将sum置0
void GetSubMaxSum(int srcBuffer[],int srcBufferLen,int maxSubBuffer[],int& maxSubLength,int& maxSum)
{
if(srcBuffer == NULL || srcBufferLen <= 0)
{
maxSubBuffer = NULL;
maxSum = 0;
return;
}
maxSum = 0;
int maxSubBufferLen = 0;
int sum = 0;
int beginIndex = 0;
int endIndex = 0;
for(int i = 0; i < srcBufferLen; i++)
{
sum +=srcBuffer[i];
if(sum > maxSum)
{
endIndex = i;
maxSum = sum;
}
if(sum <= 0)
{
beginIndex = i;
sum=0;
}
}
maxSubLength = 0;
for(int i = beginIndex; i <=endIndex; i++)
{
maxSubBuffer[maxSubLength++]=srcBuffer[i];
}
}
测试代码如下
int _tmain(int argc, _TCHAR* argv[])
{
const int srcLength = 10;
int srcBuffer[srcLength] = {0};
cout<<"please input 10 int valude"<<endl;
for(int i = 0; i < srcLength;i++)
{
cin>>srcBuffer[i];
}
int maxSubBuffer[srcLength] = {0};
int maxSum = 0;
int maxSubLength = 0;
GetSubMaxSum(srcBuffer,srcLength,maxSubBuffer,maxSubLength,maxSum);
cout<<"maxsum = "<<maxSum<<endl;
for(int i = 0; i < maxSubLength; i++)
{
cout<<maxSubBuffer[i]<<" ";
}
cout<<endl;
return 0;
}
