查看“︁最大子数列问题”︁的源代码

在[[计算机科学]]中，'''最大子数列问题'''（{{lang-en|Maximum subarray problem}}）的目标是在数列的一维方向找到一个连续的子数列，使该子数列的和最大。例如，对一个数列[&minus;2, 1, &minus;3, 4, &minus;1, 2, 1, &minus;5, 4]，其连续子数列中和最大的是[4, &minus;1, 2, 1], 其和为6。
[[File:Maximum_Subarray_Visualization.svg|缩略图|展示[2, 3, -1, -20, 5, 10]子数列之和随着子序列起始位置变化而改变，图中每条线的一点都代表一种可能的连续子序列，y轴代表所选序列之和，x轴代表所选序列的终点，每种颜色开始都从x轴的不同位置开始，代表所选序列的起点位置]]
该问题最初由[[布朗大学]]的{{le|烏爾夫·格雷南德|Ulf Grenander}}教授于1977年提出，当初他为了展示数字图像中一个简单的[[最大似然估计]]模型。不久之后[[卡内基梅隆大学]]的{{le|約瑟夫·博恩·卡丹|Joseph Born Kadane|傑·卡丹}}提出了该问题的线性算法。{{harv|Bentley|1984}}。

==卡丹算法==
卡丹算法扫描一次整个数列的所有数值，在每一个扫描点计算以该点数值为结束点的子数列的最大和（正数和）。该子数列由两部分组成：以前一个位置为结束点的最大子数列、该位置的数值。因为该算法用到了“最佳子结构”（以每个位置为终点的最大子数列都是基于其前一位置的最大子数列计算得出），该算法可看成[[动态规划]]的一个例子。

算法可用如下[[Python]]代码实现：
<syntaxhighlight lang="python">
def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
</syntaxhighlight>

该问题的一个变种是：如果数列中含有负数元素，允许返回长度为零的子数列。该问题可用如下代码解决：
<syntaxhighlight lang="python">
def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far
</syntaxhighlight>

这种算法稍作修改就可以记录最大子数列的起始位置。卡丹算法时间复杂度为<math>\mathcal{O}(n)</math>，空间复杂度为<math>\mathcal{O}(1)</math>。

==引用==
*{{citation
 | first = Jon | last = Bentley | authorlink = 喬恩·本特利 (計算機科學家)
 | title = Programming pearls: algorithm design techniques
 | journal = [[Communications of the ACM]]
 | volume = 27 | issue = 9 | year = 1984 | doi = 10.1145/358234.381162 | pages = 865–873}}.
*{{citation
 | first1 = Gerth Stølting | last1 = Brodal | first2 = Allan Grønlund | last2 = Jørgensen
 | contribution = A linear time algorithm for the ''k'' maximal sums problem
 | title = Mathematical Foundations of Computer Science 2007
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | volume = 4708 | year = 2007 | pages = 442–453 | doi = 10.1007/978-3-540-74456-6_40}}.
*{{citation | first = T. | last = Takaoka | title = Efficient algorithms for the maximum subarray problem by distance matrix multiplication | journal = Electronic Notes in Theoretical Computer Science | volume = 61 | year = 2002 | url = http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf | access-date = 2014-10-02 | archive-url = https://web.archive.org/web/20131029172313/http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf | archive-date = 2013-10-29 | dead-url = yes }}.

==外部链接==
* [http://www.algorithmist.com/index.php/Kadane's_Algorithm www.algorithmist.com] {{Wayback|url=http://www.algorithmist.com/index.php/Kadane%27s_Algorithm |date=20181227101624 }}
* [http://alexeigor.wikidot.com/kadane alexeigor.wikidot.com] {{Wayback|url=http://alexeigor.wikidot.com/kadane |date=20080128164714 }}
* [https://web.archive.org/web/20150616082206/http://www.cs.waikato.ac.nz/Teaching/COMP317B/Week_1/AlgorithmDesignTechniques.pdf Algorithm Design Techniques]

[[Category:动态规划]]