[数据结构与算法]数据结构_1.基本概念_1.3应用实例：最大子列和问题

1.3 应用实例：最大子列和问题

1.3.1应用实例-算法1&2

给定N个整数的序列{$A_1,A_2...,A_N$}，求函数$f(i,j)=max(0,\sum _{i=1}^n{A}_k)$的最大值

• 算法1

int MaxSubseqSum1(int A[],int N){
    int ThisSum,MaxSum=0;
    int i,j,k;
    for(i=0;i<N;i++){//i是子列左端位置
        for(j=i;j<N;j++){//j是子列右端位置
            ThisSum=0;//ThisSum是从A[i]到A[j]的子列和
            for(k=i;k<=j;k++){
                ThisSum+=A[k];
            }
            if(ThisSum>MaxSum)//如果刚得到的这个子列和更大
                MaxSum=ThisSum;//则更新结果
        }
    }
return MaxSum;
}

时间复杂度$T(N)=O(N^3)$
在K循环中浪费了大量的时间，当i不变，j++时，完全没必要从头算起，只需在已算出的ThisSum后再+j即可，故改进为算法2

• 算法2

int MaxSubseqSum1(int A[],int N){
    int ThisSum=0,MaxSum=0;
    int i,j,k;
    for(i=0;i<N;i++){//i是子列左端位置
        for(j=i;j<N;j++){//j是子列右端位置
            ThisSum+=A[j];//对于相同的i,不同的j,只要在j-1次循环的基础上累加1项即可
            if(ThisSum>MaxSum)//如果刚得到的这个子列和更大
                MaxSum=ThisSum;//则更新结果
        }
    }
return MaxSum;
}

时间复杂度$T(N)=O(N^2)$
一般$O(N^2)$的复杂度，通过二分方法，都可以降到$nlogn$，故改进为算法3（分而治之）

1.3.2应用实例-算法3：分而治之

• 算法3
  递归的思想
  

1. 把数组从中间一分为二，然后递归地去分别找出左右两边的最大子列和。
2. 考虑跨越边界的最大子列和，即从中间开始，往左边扫描，然后往右边扫描
3. 返回这三个结果中的最大值。

整个的时间复杂度$T(N)$，分成两半后，左右两边规模减半，即两边的时间复杂度都为$T(N/2)$。中间的向左向右每个元素都扫描一次，所以中间的复杂度是N的一个常数倍$O(N)$
故得到： ??? $T(N)=2T(N/2)+cN,T(1)=O(1)$
??? ???? 将N替换成N/2，再将$T(N/2)$代入上式得：
??? ???? $T(N)=2[2T(N/2^2)+cN/2]+cN$
? ??????? ???? $=2^{2}T(N/2^2)+2cN$
? ??????? ???? $=2^{k}O(1)+ckN$? 其中$N/2^K=1$
这一步为展开直到T()里面的数到1为止，展开了k步后得到上面这个式子，其中$k={\log }_2^N$，两项的复杂度分别为$O(N),O(NlogN)$，两个复杂度相加取大的那个，故：
??? ???? $T(N)=O(NlogN)$

int Max(int A, int B, int C)
{
    if (A > B) {
        if (A > C)
            return A;
        else
            return C;
    }
    else if (B > C)
        return B;
    else return C;
}

int DivideAndConquer(int List[], int left, int right) {
    int MaxLeftSum, MaxRightSum;
    int MaxLeftBoardSum, MaxRightBoardSum;
    int LeftBoardSum, RightBoardSum;
    int center,i;

    if (left == right) {/*递归终止条件*/
        if (List[left] > 0)
            return List[left];
        else
            return 0;
    }

    center = (right + left) / 2;
    MaxLeftSum = DivideAndConquer(List, left, center);
    MaxRightSum= DivideAndConquer(List, center+1, right);

    MaxLeftBoardSum = 0; 
    LeftBoardSum = 0;
    for (i = center;i >= left; i--)
        LeftBoardSum += List[i];
    if (LeftBoardSum > MaxLeftBoardSum)
        MaxLeftBoardSum = LeftBoardSum;
    
    MaxRightBoardSum = 0; 
    RightBoardSum = 0;
    for (i = center + 1; i <= right; i++)
        RightBoardSum += List[i];
    if (RightBoardSum > MaxRightBoardSum)
        MaxRightBoardSum = RightBoardSum;

    return Max(MaxLeftSum, MaxRightSum, MaxRightBoardSum + MaxLeftBoardSum);
}

int MaxSubseqSum3(int A[], int N)
{
    return DivideAndConquer(A, 0, N-1);
}

算法3的代码从博主CrownP的文章中学习得到

1.3.3应用实例-算法4：分而治之

int MaxSubsquSum4(int A[],int N){
    int ThisSum=0,MaxSum=0;
    for(int i=0;i<N;i++){
        ThisSum+=A[i];//向右累加
        if(ThisSum>MaxSum){
            MaxSum=ThisSum;
        }
        else if(ThisSum<0){//如果当前子列和为负
            ThisSum=0;//则不可能使后面的部分的和增大，只能使后面的和减小，故将现在的这部分子列全部抛弃
        }
    }
    return MaxSum;
}

$T(N)=O(N)$
“在线”的意思使指每输入一个数据就进行计时处理，在任何一个地方中止输入，算法都能正确给出当前的解。