一个整型数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组的和的最大值，例如输入的数组为1,-2,3,10,-4,7,2,-5，那么最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18
int MaxSum(int* a,int n)
{
int MaxSum=a[0];
int TempSum=0;
for (int i=0;i<n;i++)
{
TempSum=a[i];
for (int j=i+1;j<n;j++)
{
bool ContinueAdd=true;
if (a[j]>=0)
{
TempSum+=a[j];
}
else if (a[j]<0)
{
int tmpAJ=a[j];
for (int m=j;m<n;m++)
{
tmpAJ+=a[m];
if (tmpAJ>=0)
{
TempSum+=a[j];
break;
}
}
if(tmpAJ<0)
ContinueAdd=false;
}
if (!ContinueAdd)
{
break;
}
}
if(TempSum>MaxSum)
MaxSum=TempSum;
}
return MaxSum;
}
int main()
{
//int A[]={1,-2,3,10,-4,7,2,-5};
int B[]={-11,-22,-3};
int temp=MaxSum(B,3);
cout<<temp;
return 0;
}
实现过程虽然有点麻烦，但还是比较容易理解，牺牲了算法复杂度
当若要求时间复杂度为O(n)。
int MaxSum(int* a,int n)
{
int sum = a[n-1];
int max = a[n-1];
for(int i=0;i<n-1;i++)
{
sum = sum + a[n-i-1];
if(a[n-i-1] >= 0)
{
if(max < sum)
{
max = sum ;
}
}
if(sum < 0)
{
sum = a[n-i-1];
}
}
return max;
}
void main()
{
int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
int B[]={-22,-11,-3};
int max = MaxSum(a,8);
cout<<max;
}
这两种方法，欢迎大家提出意见，由于测试的数据比较少，可能存在bug，欢迎指正