Maximum Subarray

定义 Definition

maximum subarray（最大子数组）：在一个数列（数组）中，找出连续的一段元素，使其元素之和最大；这一段称为“最大子数组”。常见于算法与编程面试题（典型解法是 Kadane 算法）。在某些语境下也可泛指“连续子序列的最大和问题”。

发音 Pronunciation (IPA)

/ˈmæksɪməm ˈsʌbˌɛreɪ/

例句 Examples

The maximum subarray of \[-2, 1, -3, 4, -1, 2, 1, -5, 4\] is \[4, -1, 2, 1\].
数组 \[-2, 1, -3, 4, -1, 2, 1, -5, 4\] 的最大子数组是 \[4, -1, 2, 1\]。

Using Kadane’s algorithm, we can compute the maximum subarray sum in linear time even when the array contains negative numbers.
使用 Kadane 算法，即使数组包含负数，我们也能在线性时间内计算最大子数组和。

词源 Etymology

maximum 源自拉丁语 maximus（“最大的”）。
subarray 由前缀 **sub-**（“下级的、部分的”）+ array（“数组”）构成，表示“数组中的一段（通常指连续的一段）”。合起来即“数组中使某指标（通常是和）达到最大的一段连续子数组”。

文学与著作 Literary Works & Notable Uses

Introduction to Algorithms（CLRS，《算法导论》）：经典地讨论“最大子数组问题（Maximum-Subarray Problem）”并给出分治与线性解法思路。
The Algorithm Design Manual（Steven S. Skiena，《算法设计手册》）：在算法设计与常见问题模式中提及此类“最大连续和”问题。
Competitive Programming（Halims，《程序设计竞赛》系列）：常以“maximum subarray”作为基础训练题型与 Kadane 算法示例。