用分治法求最大子段和
这是我的代码,但是一运行就出现如下结果:

#include <iostream>

using namespace std;
//使用分治算法
int maxSubSum(int* a,int left,int right,int &start,int &end)
{
    int sum=0;
    if(left==right)
    {
        sum=a[left]>0? a[left]:0;
        start=end=left;
    }
    else
    {
        int center=(left+right)/2;
        int leftSum=maxSubSum(a,left,center,start,end);
        int rightSum=maxSubSum(a,center+1,right,start,end);
        int s1=0;
        int lefts=0;
        for(int i=center;i>=left;i--)
        {
            lefts+=a[i];
            if(lefts>s1)
            {
                s1=lefts;
                start=i;
            }

        }
        int s2=0;
        int rights=0;
        for(int i=center;i<=right;i--)
        {
            lefts+=a[i];
            if(rights>s2)
            {
                s2=rights;
                end=i;
            }

        }
        sum=s1+s2;
        if(sum<leftSum)
        sum=leftSum;
        if(sum<rightSum)
        sum=rightSum;
    }
    return sum;
}
int maxSum(int *a,int n,int &start,int &end)
{
    return maxSubSum(a,0,n,start,end);
}
int main()
{
    int number;
    cin>>number;
    for(int j=1;j<=number;j++)
    {
        int n,start,end,maxsum;
        cin>>n;
        int *a=new int[n];
        for(int i=0;i<n;i++)
        {
            cin>>a[i]; 
 
        }
//        for(int i=0;i<n;i++)
//        {
//            int thisSum=0;
//            for(int k=i;k<n;k++)
//            {
//                thisSum+=a[k];
//                if(thisSum>maxSum)
//                {
//                    maxSum=thisSum;
//                    start=i;
//                    end=k;
//                }
//            }
//        }
        maxsum=maxSum(a,n-1,start,end);
        cout<<"Case "<<j<<":"<<endl;
        cout<<maxsum<<" "<<++start<<" "<<++end;
        if(j!=number)
        cout<<endl<<endl;
        else
        cout<<endl;
    }
    return 0;
}

int s2=0;
        int rights=0;
        for(int i=center;i<=right;i--)
        {
            lefts+=a[i]; // 不懂代码什么原理,不过这里的lefts是不是写错了,应该用rights吧???
            if(rights>s2)
            {
                s2=rights;
                end=i;
            }
 
        }

题意：最大子段和
思路：见博客的链接
注意：犯很低级的错误，找一个数组的最大值的时候wa啦一次！
#include <iostream>
#include<cstring>
#define MAX 10010
int a[MAX],dp[MAX];
using namespace std;
int main()
{
    int n,i,m;
    while(cin >> n&&n)
    {
        memset(dp,0,sizeof(dp));
        m=0;
        for(i=1; i<=n; i++) 
 
            cin >> a[i];
        for(i=1; i<=n; i++)
        {
            dp[i+1]=a[i]+max(dp[i],0);
            if(dp[i+1]>m) m=dp[i+1];
        }
        if(m>0) cout << "The maximum winning streak is " << m << "." << endl;
        else   cout << "Losing streak." << endl;
    }
    return 0;
}

//分治法
#include <iostream>
using namespace std;
int maxsum(int a[],int left,int right)
{
int sum=0;
int i,j,s1,s2,lefts,rights,center,leftsum,rightsum;
if(left==right)
{
if(a[left]>0)
sum=a[left];
else 
sum=0;
}
else
{
center=(left+right)/2;
leftsum=maxsum(a,left,center);
rightsum=maxsum(a,center+1,right);
s1=0;lefts=0;
for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
s2=0;rights=0;
for(j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<leftsum)
sum=leftsum;
if(sum<rightsum)
sum=rightsum;
}
return sum;
}


void main()
{
int a[100];
int n,i,l,r;
cout<<"输入序列元素个数:";
cin>>n;
cout<<"输入序列元素:"<<endl;
for(i=1;i<=n;i++)
cin>>a[i];
l=n%2;
r=n-l;
cout<<"最大子段和为:"<<maxsum(a,l,r)<<endl;

}