UDN-企业互联网技术人气社区

板块导航

浏览  : 1121
回复  : 0

[其它] 经典算法问题 - 最大连续子数列和

[复制链接]
呵呵燕的头像 楼主
发表于 2016-9-24 09:49:05 | 显示全部楼层 |阅读模式
  最大连续子数列和一道很经典的算法问题,给定一个数列,其中可能有正数也可能有负数,我们的任务是找出其中连续的一个子数列(不允许空序列),使它们的和尽可能大。我们一起用多种方式,逐步优化解决这个问题。

  为了更清晰的理解问题,首先我们先看一组数据:

  8

  -2 6 -1 5 4 -7 2 3

  第一行的8是说序列的长度是8,然后第二行有8个数字,即待计算的序列。

  对于这个序列,我们的答案应该是14,所选的数列是从第2个数到第5个数,这4个数的和是所有子数列中最大的。

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

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

  1.   #include

  2.   //N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组

  3.   int N, num[1024];

  4.   int main()

  5.   {

  6.   //输入数据

  7.   scanf("%d", &N);

  8.   for(int i = 1; i <= N; i++)

  9.   scanf("%d", &num[i]);

  10.   int ans = num[1]; //ans保存最大子序列和,初始化为num[1]能保证最终结果正确

  11.   //i和j分别是枚举的子序列的起点和终点,k所在循环计算每个子序列的和

  12.   for(int i = 1; i <= N; i++) {

  13.   for(int j = i; j <= N; j++) {

  14.   int s = 0;

  15.   for(int k = i; k <= j; k++) {

  16.   s += num[k];

  17.   }

  18.   if(s > ans) ans = s;

  19.   }

  20.   }

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

  22.   return 0;

  23.   }
复制代码


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

  一个简单的优化

  如果你读懂了刚才的程序,我们可以来看一个简单的优化。

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

  
  1. #include

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

  3.   int N, num[16384], sum[16384];

  4.   int main()

  5.   {

  6.   //输入数据

  7.   scanf("%d", &N);

  8.   for(int i = 1; i <= N; i++)

  9.   scanf("%d", &num[i]);

  10.   //计算数组前缀和

  11.   sum[0] = 0;

  12.   for(int i = 1; i <= N; i++) {

  13.   sum[i] = num[i] + sum[i - 1];

  14.   }

  15.   int ans = num[1]; //ans保存最大子序列和,初始化为num[1]能保证最终结果正确

  16.   //i和j分别是枚举的子序列的起点和终点

  17.   for(int i = 1; i <= N; i++) {

  18.   for(int j = i; j <= N; j++) {

  19.   int s = sum[j] - sum[i - 1];

  20.   if(s > ans) ans = s;

  21.   }

  22.   }

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

  24.   return 0;

  25.   }
复制代码


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

  换个思路,继续优化

  你应该听说过分治法,正是:分而治之。我们有一个很复杂的大问题,很难直接解决它,但是我们发现可以把问题划分成子问题,如果子问题规模还是太大,并且它还可以继续划分,那就继续划分下去。直到这些子问题的规模已经很容易解决了,那么就把所有的子问题都解决,最后把所有的子问题合并,我们就得到复杂大问题的答案了。可能说起来简单,但是仍不知道怎么做,接下来分析这个问题:

  首先,我们可以把整个序列平均分成左右两部分,答案则会在以下三种情况中:

  1、所求序列完全包含在左半部分的序列中。

  2、所求序列完全包含在右半部分的序列中。

  3、所求序列刚好横跨分割点,即左右序列各占一部分。

  前两种情况和大问题一样,只是规模小了些,如果三个子问题都能解决,那么答案就是三个结果的最大值。我们主要研究一下第三种情况如何解决:

962542632.png


  我们只要计算出:以分割点为起点向左的最大连续序列和、以分割点为起点向右的最大连续序列和,这两个结果的和就是第三种情况的答案。因为已知起点,所以这两个结果都能在O(N)的时间复杂度能算出来。

  递归不断减小问题的规模,直到序列长度为1的时候,那答案就是序列中那个数字。

  综上所述,C语言代码如下,递归实现:

  1.   #include

  2.   //N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组

  3.   int N, num[16777216];

  4.   int solve(int left, int right)

  5.   {

  6.   //序列长度为1时

  7.   if(left == right)

  8.   return num[left];

  9.   //划分为两个规模更小的问题

  10.   int mid = left + right >> 1;

  11.   int lans = solve(left, mid);

  12.   int rans = solve(mid + 1, right);

  13.   //横跨分割点的情况

  14.   int sum = 0, lmax = num[mid], rmax = num[mid + 1];

  15.   for(int i = mid; i >= left; i--) {

  16.   sum += num[i];

  17.   if(sum > lmax) lmax = sum;

  18.   }

  19.   sum = 0;

  20.   for(int i = mid + 1; i <= right; i++) {

  21.   sum += num[i];

  22.   if(sum > rmax) rmax = sum;

  23.   }

  24.   //答案是三种情况的最大值

  25.   int ans = lmax + rmax;

  26.   if(lans > ans) ans = lans;

  27.   if(rans > ans) ans = rans;

  28.   return ans;

  29.   }

  30.   int main()

  31.   {

  32.   //输入数据

  33.   scanf("%d", &N);

  34.   for(int i = 1; i <= N; i++)

  35.   scanf("%d", &num[i]);

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

  37.   return 0;

  38.   }
复制代码


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

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

  很多动态规划算法非常像数学中的递推。我们如果能找到一个合适的递推公式,就能很容易的解决问题。

  我们用dp[n]表示以第n个数结尾的最大连续子序列的和,于是存在以下递推公式:

  
  1. dp[n] = max(0, dp[n-1]) + num[n]
复制代码

  仔细思考后不难发现这个递推公式是正确的,则整个问题的答案是max(dp[m]) | m∈[1, N]。C语言代码如下:

 
  1.  #include

  2.   //N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组

  3.   int N, num[134217728];

  4.   int main()

  5.   {

  6.   //输入数据

  7.   scanf("%d", &N);

  8.   for(int i = 1; i <= N; i++)

  9.   scanf("%d", &num[i]);

  10.   num[0] = 0;

  11.   int ans = num[1];

  12.   for(int i = 1; i <= N; i++) {

  13.   if(num[i - 1] > 0) num[i] += num[i - 1];

  14.   else num[i] += 0;

  15.   if(num[i] > ans) ans = num[i];

  16.   }

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

  18.   return 0;

  19.   }
复制代码


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

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

  考虑我们之前O(N^2)的算法,即一个简单的优化一节,我们还有没有办法优化这个算法呢?答案是肯定的!

  我们已知一个sum数组,sum表示第1个数到第i个数的和,于是sum[j] - sum[i-1]表示第i个数到第j个数的和。

  那么,以第n个数为结尾的最大子序列和有什么特点?假设这个子序列的起点是m,于是结果为sum[n] - sum[m-1]。并且,sum[m]必然是sum[1],sum[2]...sum[n-1]中的最小值!这样,我们如果在维护计算sum数组的时候,同时维护之前的最小值, 那么答案也就出来了!为了节省内存,我们还是只用一个num数组。C语言代码如下:

 
  1.  #include

  2.   //N是数组长度,num是待计算的数组,放在全局区是因为可以开很大的数组

  3.   int N, num[134217728];

  4.   int main()

  5.   {

  6.   //输入数据

  7.   scanf("%d", &N);

  8.   for(int i = 1; i <= N; i++)

  9.   scanf("%d", &num[i]);

  10.   //计算数组前缀和,并在此过程中得到答案

  11.   num[0] = 0;

  12.   int ans = num[1], lmin = 0;

  13.   for(int i = 1; i <= N; i++) {

  14.   num[i] += num[i - 1];

  15.   if(num[i] - lmin > ans)

  16.   ans = num[i] - lmin;

  17.   if(num[i] < lmin)

  18.   lmin = num[i];

  19.   }

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

  21.   return 0;

  22.   }
复制代码


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

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

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

  
  1. #include

  2.   int main()

  3.   {

  4.   int N, n, s, ans, m = 0;

  5.   scanf("%d%d", &N, &n);

  6.   ans = s = n;

  7.   for(int i = 1; i < N; i++) {

  8.   if(s < m) m = s;

  9.   scanf("%d", &n);

  10.   s += n;

  11.   if(s - m > ans)

  12.   ans = s - m;

  13.   }

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

  15.   return 0;

  16.   }
复制代码


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

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

原文作者:凌乱  来源:开发者头条

相关帖子

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部