1. 问题描述

给定整数 A1，A2，A3，….，AN（有可能为负数），求第二章最大子序列和问题和习题 2.24 - 图1 的最大值（为了方便起见，如果所有的整数均为负数，则最大子序列和为0）

2. 分析题目

（1）为什么为了方便起见，如果所有的整数均为负数，则最大子序列和为0？

因为若都是负数，则正常来说，最大子序列的和就是其中最大的负数，这样来说很容易进行求解。在这里为了求解的方便，我们这样设定，目的是为了方便编程。具体可以见解法三。
同样，我们可以考虑其对称问题，若所有的整数都是正数，此时最大的和的子序列，就是其序列本身，也没有求解的意义。
这样我们发现，只有序列中正负相间，才有求解的必要。

3. 代码实现

解法一：暴力求解

int MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum,MaxSum=0,i,j,k;
    for(i=0;i<N;i++)
    {
        for(j=i;j<N;j++)//用i标志子序列的起点，用j标志子序列的终点
        {
            ThisSum=0;
            for(k=i;k<=j;j++)//k用于遍历i和j框选好的子序列
            {
                ThisSum+=A[k];
            }
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}

时间复杂度为O（n^3）.

解法二：对暴力求解的优化

注意到，当i固定的时候，j每增加1，k所遍历的子序列仅仅加一个元素，不需要重复计算这些子序列的值，只需要在前一个子序列的基础上加一个元素即可。

int 
MaxSubsequenceSum(const int A[],int N)
{
    int ThisSum,MaxSum=0,i,j,k;
    for(i=0;i<N;i++)
    {
        ThisSum=0;
        for(j=i;j<N;j++)
        {
            ThisSum+=a[j];
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
        }
    }
    return MaxSum;
}

解法三：分治算法

算法思想：把问题分成两个大致相等的子问题，然后递归地对它们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。
具体步骤：在该问题中，如果把序列从中间分为两部分，那么最大子序列和可能在三处出现，要么整个出现在输入数据的左半部，要么整个出现在右半部，要么跨越分界线。前两种情况可以递归求解，第三种情况的最大和可以通过求出前半部分（包括前半部分的最后一个元素）的最大和以及后半部分（包含后半部分的第一个元素）的最大和而得到，此时将两个和相加。【此处是书中的原话，大概意思就是从中间往两边走，找到一个“中间序列”】
书中有更详细的解释，如果不理解可以参考书。

代码实现：

int 
MaxSum(const A[],int Left,int Right)
{
    int MaxLeftSum,MaxRightSum;
    int MaxLeftBorderSum,MaxRightBorderSum;
    int LeftBorderSum,RightBorderSum;
    int Center ,i;
    if(left==right){//此时序列只有一个值
        //终止条件
        if(arr[left]>0){//在大于0的情况下，等于其本身
            return arr[left];
        }
        else{
            return 0;//映衬题目的规则：序列不能同时为负
        }
    }
    Center=(Left+Right)/2;
    MaxLeftSum=MaxSum(A,Left,Center);
    MaxRightSum=MaxSum(A,Center+1,Right);
    //找到“中间序列”的左最大值
    MaxLeftBorderSum=0;//设置为0，则说明此时可能值最小为0
    //映衬题目的规则：序列不能同时为负
    //MaxRightBorderSum 同
    LeftBorderSum=0;
    for(i=Center;i>=Left;i--)
    {
        LeftBorderSum+=a[i];
        if(LeftBorderSum>MaxLeftBorderSum)
            MaxLeftBorderSum=LeftBorderSum;
    }
    // //找到“中间序列”的右最大值
    MaxRightBorderSum=0;RightBorderSum=0;
    for(i=Center+1;i<=Right;i++)
    {
        RightBorderSum=0;
        if(RightBorderSum>MaxRightBorderSum)
            MaxRightBorderSum=RightBorderSum;
    }
    return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);//比较函数
    //取三个数的最大值，没有实现，如果想要运行成功，需要实现以下
}
int 
MaxSubsequenceSum(const int A[],int N)
{
    return MaxSum(A,0,N-1);
}

下面是我自己写的，变量名可能和上文不太一致，但是可以正确的运行：

#include <bits/stdc++.h>
using namespace std;
int maxSubSum(int arr[],int left,int right){
    if(left==right){
        if(arr[left]>0){
            return arr[left];
        }
        else{
            return 0;
        }
    }
    int center=(left+right)/2;
    int maxLeftSum=maxSubSum(arr,left,center);
    int maxRightSum=maxSubSum(arr,center+1,right);
    int borderLeftSum=0,maxBorderLeftSum=0;
    for(int i=center;i>=left;i--){
        borderLeftSum+=arr[i];
        if(borderLeftSum>maxBorderLeftSum){
            maxBorderLeftSum=borderLeftSum;
        }
    }
    int borderRightSum=0,maxBorderRightSum=0;
    for(int i=center+1;i<=right;i++){
        borderRightSum+=arr[i];
        if(borderRightSum>maxBorderRightSum){
            maxBorderRightSum=borderRightSum;
        }
    }
    int temp=max(maxLeftSum,maxRightSum);
    return max(temp,maxBorderRightSum+maxBorderLeftSum);
}
int main(){
    int arr[6]={-2,11,-4,13,-5,-2};
    printf("%d\n",maxSubSum(arr,0,5));
}

我们发现，如果将递归基(也就是4-11行）改成:

if(right==left){
    return arr[left];
}

并将 maxBorderRightSum 和 maxBorderLeftSum 的初值改成 -inf（表示负的最大值），那么我们可以处理的序列便可以是全负的，此时初值的改变会导致处理范围的改变。
2019.12.30 复习
最大子序列和问题 P17.cpp
感悟：我们要注意到，分界线是在 center和center+1之间的。
2019.12.30 时间复杂度的粗略分析
假设所用的时间为T（N），意思是关于N的一个函数，则该方法采用了分支算法，且在求“中间序列”的过程中最坏情况下扫描了整个数组，所以 T（N）=2*T（N/2）+N。递归基作为终止条件，我们可以知道T（1）=1，根据所分析的我们可以知道：

T（2）=4=2*2
T（4）=12=4*3
T（8）=32=8*4

由此可见，T（N）=N*（logN+1）。
故而时间复杂度是O（NlogN）

习题 2.24

如果让 MaxLeftSum=MaxSubSum（A,Left,Center-1）
MaxRightSum=MaxSubSum（A,Center，Right）
则该算法不能正确的终止，考虑left=0，right=1，center=0，center-1=-1，无法终止运行，最主要的原因是：
MaxSubSum(A,0,1)中又包含了其本身，导致了无限循环。

解法四：最优起点

规律一：在求解中，我们发现最大子序列的第一个元素总是正的，因为如果“最大子序列”第一个元素是负的，那么我们总能找到一个序列，其和比“最大子序列”要大。同样，对于最大子序列，前缀不可能是和为负的子序列。

通过上述的归纳，我们便可以更快的理解此解法了。

int 
MaxSubsequenceSum(const int A[])
{
    int ThisSum,MaxSum;
    int i;
    ThisSum=0;MaxSum=0;
    for(i=0;i<N;i++)
    {
        ThisSum+=A[i];
        if(ThisSum>MaxSum)
            MaxSum=ThisSum;
        else if(ThisSum<0)//这个相当于“积累量”的判断
            //如果前面的积累量为负，则直接将 ThisSum 清零（因为保留对结果也没有贡献度）
            //如果前面的积累为正，则对最终结果有可能有贡献度
            ThisSum=0;
    }
    return MaxSum;
}

复习2019.12.30 ：
感悟写在上文代码中。
最大子序列求和问题最优解法.cpp
2019.12.31 补充
特性

该算法只对数据进行一次扫描，当A[i]被读入并处理之后，它就不需要再被存储。
另外，在任意的时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。

拥有这些特性的算法叫做联机算法（on-line algorithm）。
特点：需要常量的空间，以线性时间运行。

参考资料：

最大子序列和的四种算法 //此文简短的描述了原理，还附有java代码
数据结构与算法分析学习笔记——最大子序列求和问题 //摘录了此文的代码（也是书中的代码）

第二章 最大子序列和问题 和习题 2.24