算法笔记:“最大子列和”问题的算法进化历程(C/C++)

2018年8月28日 3 条评论 130 次阅读 1 人点赞

问题描述

最大子列和问题:给定已知长度的整数数列,找出其中一段连续的子数列,使得该子数列的和最大。

用数学语言描述为:给定长度为 \( n \) 的整数数列\( \left \{ A_1, A_2, A_3, ..., A_n \right \} \),求函数

$$ f(i,j)=max \left \{ 0,\sum_{k=i}^{j}A_k \right \} $$

的最大值。

 

本文将依次讲解解决这一问题的 4 个逐渐优化(指时间复杂度)的算法,且采用伪代码C/C++ 语言进行描述。

本文地址:https://www.jedbit.com/article/maximum-subarray-algorithm.html

算法 1:非常暴力的暴力求解

既然要求最大子列和,那就把所有的子列和全部求出来,然后取最大的一个就行了。这就是暴力求解

伪代码

procedure 最大子列和算法1 (输入: 有n个数的数列A):
    maxSum = 0    // 初始化最大和为0
    for i = 0 to n:    // 子列左端
        for j = i to n:    // 子列右端
            tempSum = 0    // 当前子列和初始化为0
            for k = i to j:
                tempSum += A[k]
            if tempSum > maxSum:    // 若当前子列和大于已储存的最大和
                maxSum = tempSum    // 则更新最大和
    return maxSum

C/C++ 代码

int max_subarray1(int A[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tempSum = 0;
            for (int k = i; k <= j; k++) {
                tempSum += A[k];
            }
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }
    return maxSum;
}

通过以上代码可以看出,该算法存在 3 层嵌套的 for 循环,故时间复杂度为 \( O\left ( N^3 \right ) \),一旦输入数据量很大(比如 100 万),该算法几乎没什么实际作用了。

 

算法 2:没那么暴力的暴力求解

算法 1 明显浪费时间。

在算法 1 中,计算的第一个子列为 \( \left \{ A_1 \right \} \),第二个子列为 \( \left \{ A_1, A_2 \right \} \),第三个子列为 \( \left \{ A_1, A_2, A_3 \right \} \)……当 i 固定而 j 递增的时候,每次都是从头往后求和的,从而造成了资源浪费。我们可以利用以下公式优化求和这一步骤:

$$ \sum_{k=i}^{j+1}A_k=\sum_{k=i}^{j}A_k+A_{j+1} $$

伪代码

procedure 最大子列和算法2 (输入: 有n个数的数列A):
    maxSum = 0    // 初始化最大和为0
    for i = 0 to n:    // 子列左端
        tempSum = 0    // 从A[i]到A[j]的子列和
        for j = i to n:    // 子列右端
            tempSum += A[j]
            if tempSum > maxSum:    // 若当前子列和大于已储存的最大和
                maxSum = tempSum    // 则更新最大和
    return maxSum

C/C++ 代码

int max_subarray2(int A[], int n) {
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        int tempSum = 0;    // 对于固定的i,依次求从A[i]到A[j]的子列和
        for (int j = i; j < n; j++) {
            tempSum += A[j];
            if (tempSum > maxSum) {
                maxSum = tempSum;
            }
        }
    }
    return maxSum;
}

该算法存在 2 层嵌套的 for 循环,因此时间复杂度降到了 \( O\left ( N^2 \right ) \)

 

算法 3:递归与分治

算法思想

先将最初的数组一分为二,求其①左边的最大子列和,再求其②右边的最大子列和,再找到③跨越中间边界的最大子列和,三者之中的最大值就是我们要求的整个数列的最大子列和。

整个数列 \( \left \{ A_1, ..., A_9 \right \} \) 的最大子列和,必定是①②③中的最大值。

在上图中,①和②可以通过递归的方式得到

要想得到③,首先从中间边界开始向左“扫描”,得出一个最大和;然后再从中间边界开始向右扫描,得出另一个最大和;最后把向左和向右扫描出来的最大和相加,即是③。

本文地址:https://www.jedbit.com/article/maximum-subarray-algorithm.html

限于篇幅,此处不再给出伪代码,请直接阅读 C/C++ 代码。

C/C++ 代码

int max_subarray3(int A[], int n) {
    if (n == 1) { return A[0]; }    // 若子列长度为1,则结束递归

    /* 左边的最大子列和 */
    int leftMaxSum = max_subarray3(&A[0], n / 2);

    /* 右边的最大子列和 */
    int rightMaxSum = max_subarray3(&A[n / 2], n - n / 2);

    /* 跨越中间边界的最大子列和 */
    int leftScanMaxSum = 0, rightScanMaxSum = 0;
    int tempSum = 0;
    for (int i = n / 2 - 1; i >= 0; i--) {    // 向左扫描
        tempSum += A[i];
        if (tempSum > leftScanMaxSum) { leftScanMaxSum = tempSum; }
    }
    tempSum = 0;    // 清零,供向右扫描使用
    for (int i = n / 2; i <= n; i++) {    // 向右扫描
        tempSum += A[i];
        if (tempSum > rightScanMaxSum) { rightScanMaxSum = tempSum; }
    }
    int midMaxSum = leftScanMaxSum + rightScanMaxSum;

    /* 答案是三种情况中的最大值 */
    int result = leftMaxSum;
    if (rightMaxSum > result) { result = rightMaxSum; }
    if (midMaxSum > result) { result = midMaxSum; }
    return result;
}

时间复杂度分析

递归算法的时间复杂度的分析稍稍困难一点。看到数学就头疼的同学可以跳过这段,直接看结论即可。

首先我们假设输入 \( N \) 个数据时需要进行 \( T\left ( N \right ) \) 步操作。(认为操作次数与时间成正比)

过程①和②是递归调用自身算法,但只处理一半数据,因此共需要进行 \( 2\cdot T\left ( \frac{N}{2} \right ) \) 次操作。

过程③中从边界向左、向右分别扫描了一次,因此过程③的时间复杂度应该为 \( O\left ( N \right ) \),所进行的操作次数为 \( N \) 的常数倍,设为 \( c\cdot N \)。

由此得到关于 \( T\left ( N \right ) \) 的递推关系

$$ T\left ( N \right )=2\cdot T\left ( \frac{N}{2} \right )+c\cdot N $$

$$ T\left ( 1 \right )=O\left ( 1 \right ) $$

令 \( N=2^k \),如此递推下去:

$$\begin{align*}
T\left ( N \right )&=2\cdot T\left ( \frac{N}{2} \right )+c\cdot N \\
&=2^2\cdot T\left ( \frac{N}{2^2} \right )+2\cdot c\cdot N \\
&=... \\
&=2^k\cdot T\left ( 1 \right )+k\cdot c\cdot N \\
&=N\cdot O\left ( 1 \right )+\log N\cdot c\cdot N \\
&=O\left ( N\log N \right )
\end{align*}$$

综上所述,算法 3 的时间复杂度为 \( O\left ( N\log N \right ) \)

 

算法 4:在线处理算法

所谓“在线处理”,意思就是每输入一个数据就进行即时处理。换句话说,在算法进行的任何时候中止输入,得到的结果都是在当前时刻正确的结果。

伪代码

procedure 最大子列和算法4 (输入: 有n个数的数列A):
    tempSum = 0
    maxSum = 0
    for i = 0 to N:
        tempSum += A[i]    // 依次向右累加
        if tempSum > maxSum:    // 若发现更大的子列和
            maxSum = tempSum    // 则更新当前结果
        else if tempSum < 0:    // 一旦当前子列和为负数
            tempSum = 0    // 则不可能使后续子列和变大。抛弃掉,归零
    return maxSum

C/C++ 代码

int max_subarray4(int A[], int n) {
    int tempSum = 0, maxSum = 0;
    for (int i = 0; i < n; i++) {
        tempSum += A[i];
        if (tempSum > maxSum) {
            maxSum = tempSum;
        }
        else if (tempSum < 0) {
            tempSum = 0;
        }
    }
    return maxSum;
}

该算法的时间复杂度为 \( O\left ( N \right ) \),而且这是所有可能算法中最快的了。因为无论如何,我们都至少需要扫描一遍数列中的所有元素,仅仅扫描数列就需要时间复杂度 \( O\left ( N \right ) \) ,因此不可能有更快的算法了。

 

写在后面

首次在本站使用 LaTeX 编辑数学公式,如有纰漏敬请指正!

本文出自 JedBit(www.jedbit.com),转载请注明出处。

参考资料:陈越《数据结构

本文地址:https://www.jedbit.com/article/maximum-subarray-algorithm.html

Jed

一名狂热的技术爱好者。

文章评论(3)

  • boke112导航

    博主,你好,boke112导航特来拜会,已将贵站收录到博客导航的建站技术类,谢谢支持!

    2018年8月29日
  • J2

    我就是看到公式就头疼的同学 :wink:

    2018年8月28日
  • 提示:有人回复时会邮件通知您