此题来自《数据结构与算法》，书中一共介绍了四种方法，这里贴出两种。
1.分治递归，对本题来说，虽然有更好的算法，但是用此题理解分治算法感觉挺有用
#include <iostream>
int maxsublink(int *a,int right,int left);
using std::cout;
using std::cin; int main()
{
int a[]={,-,,-,-,,,-};
int maxnum=maxsublink(a,,);
cout<<maxnum;
return ;
}
int maxsublink(int *a,int left,int right)
{
int rightmax,leftmax;
int leftbordermax,rightbordermax;
int leftborder,rightborder; if(left==right)
{
if(a[left]>)
return a[left];
else
return ;
}
int mid,i;
mid=(right+left)/;
leftmax=maxsublink(a,left,mid);
rightmax=maxsublink(a,mid+,right);
leftborder=leftbordermax=;
for(i=mid;i>=left;i--)
{
leftborder+=a[i];
if(leftborder>leftbordermax)
leftbordermax=leftborder;
}
rightborder=rightbordermax=;
for(i=mid+;i<=right;i++)
{
rightborder+=a[i];
if(rightborder>rightbordermax)
rightbordermax=rightborder;
}
int intermax=leftbordermax+rightbordermax;
if(intermax>=rightmax)
{
if(intermax>=leftmax)
return intermax;
else
return leftmax;
}
else
{
if(rightmax>=leftmax)
return rightmax;
else
return leftmax;
}
}
2.遍历整个数组，每个遍历的值保存入thissum，当thissum<0时，thissum置零；当thissum>max时，更新max
这种方法时间复杂度可以达到O(n)，感觉这种编程方法很值得学习，而且在别的算法中也经常用到，很典型。
#include <iostream> using namespace std;
int maxsublink(int *a,int num);
int main()
{
int a[]={,-,,-,-,,,-};
int maxnum=maxsublink(a,);
cout<<maxnum;
return ;
}
int maxsublink(int *a,int num)
{
int i,thissum,maxsum;
maxsum=thissum=;
for(i=;i<num;i++)
{
thissum+=a[i];
if(thissum>maxsum)
maxsum=thissum;
else if(thissum<)
thissum=;
}
return maxsum;
}