经典算法问题 - 最大连续子数列和

最大连续子数列和一道很经典的算法问题,给定一个数列,其中可能有正数也可能有负数,我们的任务是找出其中连续的一个子数列(不允许空数列),使它们的和尽可能大。我们一起用多种方式,逐步优化解决这个问题。

为了更清晰的理解问题,首先我们先看一组数据:
8
-2 6 -1 5 4 -7 2 3
第一行的8是说数列的长度是8,然后第二行有8个数字,即待计算的数列。
对于这个数列,我们的答案应该是14,所选的数列是从第2个数到第5个数,这4个数的和是所有子数列中最大的。

最暴力的做法,复杂度O(N^3)

暴力求解也是容易理解的做法,简单来说,我们只要用两层循环枚举起点和终点,这样就尝试了所有的子数列,然后计算每个子数列的和,然后找到其中最大的即可,C语言代码如下:

#include <stdio.h>

//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[1024];

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    
    int ans = num[1]; //ans保存最大子数列和,初始化为num[1]能保证最终结果正确
    //i和j分别是枚举的子数列的起点和终点,k所在循环计算每个子数列的和
    for(int i = 1; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            int s = 0;
            for(int k = i; k <= j; k++) {
                s += num[k];
            }
            if(s > ans) ans = s;
        }
    }
    printf("%d\n", ans);

    return 0;
}

这个算法的时间复杂度是O(N^3),复杂度的计算方法可参考《算法导论》第一章,如果我们的计算机可以每秒计算一亿次的话,这个算法在一秒内只能计算出500左右长度数列的答案。

一个简单的优化

如果你读懂了刚才的程序,我们可以来看一个简单的优化。
如果我们有这样一个数组sum,sum[i]表示第1个到第i个数的和。那么我们如何快速计算第i个到第j个这个数列的和?对,只要用sum[j] - sum[i-1]就可以了!这样的话,我们就可以省掉最内层的循环,让我们的程序效率更高!C语言代码如下:

#include <stdio.h>

//N是数组长度,num是待计算的数组,sum是数组前缀和,放在全局区是因为可以开很大的数组
int N, num[16384], sum[16384];

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    
    //计算数组前缀和
    sum[0] = 0;
    for(int i = 1; i <= N; i++) {
        sum[i] = num[i] + sum[i - 1];
    }

    int ans = num[1]; //ans保存最大子数列和,初始化为num[1]能保证最终结果正确
    //i和j分别是枚举的子数列的起点和终点
    for(int i = 1; i <= N; i++) {
        for(int j = i; j <= N; j++) {
            int s = sum[j] - sum[i - 1];
            if(s > ans) ans = s;
        }
    }
    printf("%d\n", ans);

    return 0;
}

这个算法的时间复杂度是O(N^2)。如果我们的计算机可以每秒计算一亿次的话,这个算法在一秒内能计算出10000左右长度数列的答案,比之前的程序已经有了很大的提升!此外,我们在这个程序中创建了一个sum数组,事实上,这也是不必要的,我们我就也可以把数组前缀和直接计算在num数组中,这样可以节约一些内存。

换个思路,继续优化

你应该听说过分治法,正是:分而治之。我们有一个很复杂的大问题,很难直接解决它,但是我们发现可以把问题划分成子问题,如果子问题规模还是太大,并且它还可以继续划分,那就继续划分下去。直到这些子问题的规模已经很容易解决了,那么就把所有的子问题都解决,最后把所有的子问题合并,我们就得到复杂大问题的答案了。可能说起来简单,但是仍不知道怎么做,接下来分析这个问题:
首先,我们可以把整个数列平均分成左右两部分,答案则会在以下三种情况中:
1、所求数列完全包含在左半部分的数列中。
2、所求数列完全包含在右半部分的数列中。
3、所求数列刚好横跨分割点,即左右数列各占一部分。
前两种情况和大问题一样,只是规模小了些,如果三个子问题都能解决,那么答案就是三个结果的最大值。我们主要研究一下第三种情况如何解决:
962542632.png
我们只要计算出:以分割点为起点向左的最大连续数列和、以分割点为起点向右的最大连续数列和,这两个结果的和就是第三种情况的答案。因为已知起点,所以这两个结果都能在O(N)的时间复杂度能算出来。
递归不断减小问题的规模,直到数列长度为1的时候,那答案就是数列中那个数字。
综上所述,C语言代码如下,递归实现:

#include <stdio.h>

//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[16777216];

int solve(int left, int right)
{
    //数列长度为1时
    if(left == right)
        return num[left];
    
    //划分为两个规模更小的问题
    int mid = left + right >> 1;
    int lans = solve(left, mid);
    int rans = solve(mid + 1, right);
    
    //横跨分割点的情况
    int sum = 0, lmax = num[mid], rmax = num[mid + 1];
    for(int i = mid; i >= left; i--) {
        sum += num[i];
        if(sum > lmax) lmax = sum;
    }
    sum = 0;
    for(int i = mid + 1; i <= right; i++) {
        sum += num[i];
        if(sum > rmax) rmax = sum;
    }

    //答案是三种情况的最大值
    int ans = lmax + rmax;
    if(lans > ans) ans = lans;
    if(rans > ans) ans = rans;

    return ans;
}

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);

    printf("%d\n", solve(1, N));

    return 0;
}

不难看出,这个算法的时间复杂度是O(N*logN)的(想想归并排序)。它可以在一秒内处理百万级别的数据,甚至千万级别也不会显得很慢!这正是算法的优美之处。对递归不太熟悉的话可能会对这个算法有所疑惑,那可就要仔细琢磨一下了。

动态规划的魅力,O(N)解决!

很多动态规划算法非常像数学中的递推。我们如果能找到一个合适的递推公式,就能很容易的解决问题。
我们用dp[n]表示以第n个数结尾的最大连续子数列的和,于是存在以下递推公式:
dp[n] = max(0, dp[n-1]) + num[n]
仔细思考后不难发现这个递推公式是正确的,则整个问题的答案是max(dp[m]) | m∈[1, N]。C语言代码如下:

#include <stdio.h>

//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[134217728];

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    
    num[0] = 0;
    int ans = num[1];
    for(int i = 1; i <= N; i++) {
        if(num[i - 1] > 0) num[i] += num[i - 1];
        else num[i] += 0;
        if(num[i] > ans) ans = num[i];
    }

    printf("%d\n", ans);

    return 0;
}

这里我们没有创建dp数组,根据递归公式的依赖关系,单独一个num数组就足以解决问题,创建一个一亿长度的数组要占用几百MB的内存!这个算法的时间复杂度是O(N)的,所以它计算一亿长度的数列也不在话下!不过你如果真的用一个这么大规模的数据来测试这个程序会很慢,因为大量的时间都耗费在程序读取数据上了!

另辟蹊径,又一个O(N)的算法

考虑我们之前O(N^2)的算法,即一个简单的优化一节,我们还有没有办法优化这个算法呢?答案是肯定的!
我们已知一个sum数组,sum[i]表示第1个数到第i个数的和,于是sum[j] - sum[i-1]表示第i个数到第j个数的和。
那么,以第n个数为结尾的最大子数列和有什么特点?假设这个子数列的起点是m,于是结果为sum[n] - sum[m-1]。并且,sum[m-1]必然是sum[1],sum[2]...sum[n-1]中的最小值!这样,我们如果在维护计算sum数组的时候,同时维护之前的最小值, 那么答案也就出来了!为了节省内存,我们还是只用一个num数组。C语言代码如下:

#include <stdio.h>

//N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组
int N, num[134217728];

int main()
{
    //输入数据
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &num[i]);
    
    //计算数组前缀和,并在此过程中得到答案
    num[0] = 0;
    int ans = num[1], lmin = 0;
    for(int i = 1; i <= N; i++) {
        num[i] += num[i - 1];
        if(num[i] - lmin > ans)
            ans = num[i] - lmin;
        if(num[i] < lmin)
            lmin = num[i];
    }

    printf("%d\n", ans);

    return 0;
}

看起来我们已经把最大连续子数列和的问题解决得很完美了,时间复杂度和空间复杂度都是O(N),不过,我们确实还可以继续!

大道至简,最大连续子数列和问题的完美解决

很显然,解决此问题的算法的时间复杂度不可能低于O(N),因为我们至少要算出整个数列的和,不过如果空间复杂度也达到了O(N),就有点说不过去了,让我们把num数组也去掉吧!

#include <stdio.h>

int main()
{
    int N, n, s, ans, m = 0;

    scanf("%d%d", &N, &n); //读取数组长度和数列中的第一个数
    ans = s = n; //把ans初始化为数列中的的第一个数
    for(int i = 1; i < N; i++) {
        if(s < m) m = s;
        scanf("%d", &n);
        s += n;
        if(s - m > ans)
            ans = s - m;
    }
    printf("%d\n", ans);

    return 0;
}

这个程序的原理和另辟蹊径,又一个O(N)的算法中介绍的一样,在计算前缀和的过程中维护之前得到的最小值。它的时间复杂度是O(N),空间复杂度是O(1),这达到了理论下限!唯一比较麻烦的是ans的初始化值,不能直接初始化为0,因为数列可能全为负数!

至此,最大连续子数列和的问题已经被我们完美解决!然而以上介绍的算法都只是直接求出问题的结果,而不能求出具体是哪一个子数列,其实搞定这个问题并不复杂,具体怎么做留待读者思考吧!

标签: none

已有 22 条评论

  1. Rafe Rafe

    oj上提交没一段过的了,我笑笑就不说话

    1. sss sss

      亲测能过,替博主平反

    2. 要稍微改一下保证数据格式没问题啊 -.-'

  2. imlk imlk

    写的很棒!

  3. 赞一个,但是有小毛病 赞一个,但是有小毛病

    楼主,刚看到你写的,很棒,可是还有小问题哦。
    int ans = num[1], lmin = 0;//这里有问题,应该是lmin=num[1]。你可以试试
    for(int i = 1; i ans)
    ans = num[i] - lmin;
    if(num[i] < lmin)
    lmin = num[i];
    }

    1. 感谢指正,已修改~
      -----------------修改自2019年3月8日
      看了楼下的评论发现之前写的是对的...再改回去

  4. 214jlho 214jlho

    我觉得前面那个同学说的毛病不对,不修改才是正确答案
    因为当输入全为正数时,将lmin初始化为0才是对的,否则最终结果会比答案小num[1]

    1. 214jlho 214jlho

      我在PAT上验证过了

      1. 我又仔细看了一遍,你说的是对的,看到上面的回复时已经是写了文章很久之后了,并没有仔细看代码,现在看来确实是改错了。

  5. 叻叻猪 叻叻猪

    我觉得对于最后一种大道至简的算法还有一种类似的算法。我们可以用还是用num[i]来存储前i项的和,但在计算的过程中,我们就可以找到num最大值和最小值的下标max和min,num[max] - num[min]即为答案。证明也不难,因为我们所找到的答案无论加上max右边多少个数和min左边多少个数其大小都不会大于我们所求的答案。所以,min和max即是最长序列的左端点和右端点。

  6. buy tadalafil online

  7. order ivermectin 6 mg

  8. 5mg cialis cost

  9. zithromax 500mg price

  10. online viagra pills

  11. mandy flores viagra

  12. tadalafil half life

  13. cvs cialis cost

  14. 20mg cialis walmart

  15. cvs cialis cost

  16. sildenafil medicine

  17. meloxicam dosage max

添加新评论