最大子列和问题的4种复杂度算法

定义：给定个整数的序列 ，求函数 的最大值(若最大子列和为负数，则返回0)。

算法1——

int MaxSubSeqSum1(int a[], int n) {
    int maxSum = 0, thisSum = 0;

    // i: 子列左端位置，j: 子列右端位置，thisSum: a[i]~a[j]的子列和
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            thisSum = 0;
            
            // 从左端加到右端，再移动右端位置
            for (int k = i; k <= j; k++) {
                thisSum += a[k];
            }
            
            // 若刚得到的这个子列和更大，则更新最大子列和的值
            maxSum = thisSum > maxSum ? thisSum : maxSum;
        }
    }
    return maxSum;
}

算法2——

int MaxSubSeqSum2(int a[], int n) {
    int maxSum = 0, thisSum = 0;

    // i: 子列左端位置，j: 子列右端位置，thisSum: a[i]~a[j]的子列和
    for (int i = 0; i < n; i++) {
        thisSum = 0;

        // 边移动边累加
        for (int j = i; j < n; j++) {
            thisSum += a[j];
            maxSum = thisSum > maxSum ? thisSum : maxSum;
        }
    }
    return maxSum;
}

算法3（分治法）——

• 总体思想

  求最大子序列和，我们可以将求最大子序列和的序列分解为两个大小相等的子序列，然后在这两个大小相等的子序列中，分别求最大子序列和，如果由原序列分解的这两个子序列还可以进行分解的话，进一步分解，直到不能进行分解为止，使问题逐步简化，最后求最简化的序列的最大子序列和，沿着分解路径逐步回退，合成为最初问题的解。

• 整体最大子列和可能出现的所有情况

  • 序列的左半部分的最大子序列和

  • 序列的右半部分的最大子序列和

  • 横跨左右得到的最大子序列和

    由 包含左半部分最后一个元素的最大子序列和 与 包含右半部分第一个元素的最大子序列和 相加所得

• 详细分析

• 代码

int Max3(int i, int j, int k) {
    int max = i;

    if (max < j) max = j;
    if (max < k) max = k;

    return max;
}

int MaxSubSeqSum_DC(int a[], int left, int right) {
    //  递归的返回条件: 当分解至左半边元素等于右半边元素，即子序列中只有一个元素时，它本身即最大子序列和，因此返回它本身
    if (left == right)
        return a[left];

    int center = (left + right) / 2;    //  左右子序列的分界点
    int L_MaxSubSeqSum = MaxSubSeqSum_DC(a, left, center);  //  左半边子序列的最大子序列和
    int R_MaxSubSeqSum = MaxSubSeqSum_DC(a, center + 1, right); //  右半边子序列的最大子序列和

    int MaxSubSeqSum_ContainLeftLast = a[center];   //  左半边子序列包含最后一个元素的最大子序列和 
    int CurSubSeqSum_ContainLeftLast = 0;   //  左半边子序列的和 用于更新 MaxSubSeqSum_ContainLeftLast

    int MaxSubSeqSum_ContainRightFirst = a[center + 1]; //  右半边子序列包含第一个元素的最大子序列和
    int CurSubSeqSum_ContainRightFirst = 0; //  右半边子序列的和 用于更新 MaxSubSeqSum_ContainRightFirst

    //  计算得出 MaxSubSeqSum_ContainLeftLast
    for (int i = center; i >= left; i--) {
        CurSubSeqSum_ContainLeftLast += a[i];
        if (CurSubSeqSum_ContainLeftLast > MaxSubSeqSum_ContainLeftLast)
            MaxSubSeqSum_ContainLeftLast = CurSubSeqSum_ContainLeftLast;
    }

    //  计算得出 MaxSubSeqSum_ContainRightFirst
    for (int j = center+1; j <= right; j++) {
        CurSubSeqSum_ContainRightFirst += a[j];
        if (CurSubSeqSum_ContainRightFirst > MaxSubSeqSum_ContainRightFirst)
            MaxSubSeqSum_ContainRightFirst = CurSubSeqSum_ContainRightFirst;
    }

    //  跨越左右半区的最大子序列和：左半边子序列包含最后一个元素的最大子序列和 + 右半边子序列包含第一个元素的最大子序列和
    int Cross_MaxSubSeqSum = MaxSubSeqSum_ContainLeftLast + MaxSubSeqSum_ContainRightFirst;

    //  返回三者中的最大值
    return Max3(L_MaxSubSeqSum, R_MaxSubSeqSum, Cross_MaxSubSeqSum);
}

//  T(n) = O(nlogn) 分治算法
int MaxSubSeqSum3(int a[], int n) {
    return MaxSubSeqSum_DC(a, 0, n - 1);
}

• 复杂度分析
  • 确定左/右半边最大子列和的时间复杂度：
  • 确定跨越左右的最大子列和的复杂度（上界）：
  • 推导

    • ————A

    • 将N替换为N/2，得到： ————B

    • 将 B 代入 A，得到：

    • 将N替换为，直到等于1，再代入A，得到：

      

      =

      =

      =

算法4（在线处理）——

int MaxSubSeqSum4(int a[], int n) {
    int maxSum = 0, thisSum = 0;

    for (int i = 0; i < n; i++) {
        thisSum += a[i];

        if (thisSum > maxSum) {
            maxSum = thisSum;
        }
        
        // 如果当前子列和为负，则直接抛弃，寻找新的起点
        else if (thisSum < 0) {
            thisSum = 0;
        }
    }
    return maxSum;
}

“在线”是指每输入一个数据就进行即时处理，在任何一个地方终止输入，算法都能正确给出当前的解。