![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Maximum_Subarray_Visualization.svg/langzh-640px-Maximum_Subarray_Visualization.svg.png&w=640&q=50)
最大子数列问题
維基百科,自由的 encyclopedia
在计算机科学中,最大子数列问题(英語:Maximum subarray problem)的目标是在数列的一维方向找到一个连续的子数列,使该子数列的和最大。例如,对一个数列[−2, 1, −3, 4, −1, 2, 1, −5, 4],其连续子数列中和最大的是[4, −1, 2, 1], 其和为6。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Maximum_Subarray_Visualization.svg/320px-Maximum_Subarray_Visualization.svg.png)
该问题最初由布朗大学的烏爾夫·格雷南德(英语:Ulf Grenander)教授于1977年提出,当初他为了展示数字图像中一个简单的最大似然估计模型。不久之后卡内基梅隆大学的傑·卡丹(英语:Joseph Born Kadane)提出了该问题的线性算法。(Bentley 1984)。