求最大子序列和，如果求出来的值为负数，则返回0。时间复杂度：O(NlogN)

maxSequenceSum.cpp

#include <iostream>
using namespace std;


int max(int a,int b,int c)
{
    return a>b?(a>c?a:c):(c>b?c:b);
}


static int MaxSubSum(const int a[],int left,int right)
{
    if (left == right)
    {
        if (a[left] > 0) 
            return a[left];
        else 
            return 0;
    }

    int center = (left+right)/2;
    
    int leftPartMaxSum = MaxSubSum(a,left,center);
    int rightPartMaxSum = MaxSubSum(a,center+1,right);

    int leftSum = 0,maxLeftSum = 0;
    int rightSum = 0,maxRightSum = 0;
    for (int i = center;i >= left;i--)
    {
        leftSum += a[i];
        if (maxLeftSum < leftSum)
            maxLeftSum = leftSum;
    }
    for (int i = center+1;i <= right;i++)
    {
        rightSum += a[i];
        if (rightSum > maxRightSum)
            maxRightSum = rightSum;
    }


    return max(leftPartMaxSum,rightPartMaxSum,maxLeftSum+maxRightSum);

}


int maxSequenceSum(const int a[],int N)
{
    return MaxSubSum(a,0,N-1);
}


int main()
{
    const int a[] = {4,-3,5,-2,-1,2,6,-2};
    int length = sizeof(a)/sizeof(a[0]);
    int max = maxSequenceSum(a,length);
    cout << "max is " << max << endl;
    return 0;
}