动态规划法(八)最大子数组问题(maximum subarray problem

问题简介

  本文将介绍计算机算法中的经典问题——最大子数组问题(maximum subarray problem)。所谓的最大子数组问题,指的是:给定一个数组A,寻找A的和最大的非空连续子数组。比如,数组 A = [-2, -3, 4, -1, -2, 1, 5, -3], 最大子数组应为[4, -1, -2, 1, 5],其和为7。

  首先,如果A中的元素全部为正(或非负数),则最大子数组就是它本身;如果A中的元素全部为负,则最大子数组就是第一个元素组成的数组。以上两种情形是平凡的,那么,如果A中的元素既有正数,又有负数,则该如何求解呢?本文将介绍该问题的四种算法,并给出后面三种算法的Python语言实现,解决该问题的算法如下:

暴力求解

分治法

Kadane算法

动态规划法

  下面就这四种算法做详细介绍。

暴力求解

  假设数组的长度为n,暴力求解方法的思路是很简单的,就是将子数组的开始坐标和结束坐标都遍历一下,这样共有n(n-1)/2中组合方式,再考虑这所有组合方式中和最大的情形即可。

  该算法的运行时间为O(n^2),效率是很低的。那么,还有其它高效的算法吗?

分治法

  分治法的基本思想是将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小,递归地求解出子问题,如果子问题的规模足够小,则停止递归,直接求解,最后将子问题的解组合成原问题的解。

  对于最大子数组,我们要寻求子数组A[low…high]的最大子数组。令mid为该子数组的中央位置,我们考虑求解两个子数组A[low…mid]和A[mid+1…high]。A[low…high]的任何连续子数组A[i…j]所处的位置必然是以下三种情况之一:

完全位于子数组A[low…mid]中,因此

low≤i≤j≤mid.

完全位于子数组A[mid+1…high]中,因此

mid

跨越了中点,因此

low≤i≤mid

因此,最大子数组必定为上述3种情况中的最大者。对于情形1和情形2,可以递归地求解,剩下的就是寻找跨越中点的最大子数组。

  任何跨越中点的子数组都是由两个子数组A[i…mid]和A[mid+1…j]组成,其中

low≤i≤mid

mid

.因此,我们只需要找出形如A[i…mid]和A[mid+1…j]的最大子数组,然后将其合并即可,这可以在线性时间内完成。过程FIND-MAX-CROSSING-SUBARRAY接收数组A和下标low、mid和high作为输入,返回一个下标元组划定跨越中点的最大子数组的边界,并返回最大子数组中值的和。其伪代码如下:

  有了FIND-MAX-CROSSING-SUBARRAY我们可以找到跨越中点的最大子数组,于是,我们也可以设计求解最大子数组问题的分治算法了,其伪代码如下:

  显然这样的分治算法对于初学者来说,有点难度,但是熟能生巧, 多学多练也就不难了。该分治算法的运行时间为

O(n∗logn).

Kadane算法

  Kadane算法的伪代码如下:

  Kadane算法的简单想法就是寻找所有连续的正的子数组(max_ending_here就是用来干这事的),同时,记录所有这些连续的正的子数组中的和最大的连续数组。每一次我们得到一个正数,就将它与max_so_far比较,如果它的值比max_so_far大,则更新max_so_far的值。

动态规划法

   用MS[i]表示最大子数组的结束下标为i的情形,则对于i-1,有:

这样就有了一个子结构,对于初始情形,

MS[1]=A[1].

遍历i, 就能得到MS这个数组,其最大者即可最大子数组的和。

MS[i]=max(MS[i−1],A[i]).

总结

   可以看到以上四种算法,每种都有各自的优缺点。对于暴力求解方法,想法最简单,但是算法效率不高。Kanade算法简单高效,但是不易想到。分治算法运行效率高,但其分支过程的设计较为麻烦。动态规划法想法巧妙,运行效率也高,但是没有普遍的适用性。

Python程序

   下面将给出分治算法,Kanade算法和动态规划法来求解最大子数组问题的Python程序, 代码如下:

输出结果如下:

参考文献

算法导论(第三版) 机械工业出版社

https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

https://algorithms.tutorialhorizon.com/dynamic-programming-maximum-subarray-problem/

注意:本人现已开通两个微信公众号: 用Python做数学(微信号为:python_math)以及轻松学会Python爬虫(微信号为:easy_web_scrape), 欢迎大家关注哦~~

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180607G0EPB400?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券