Kadane

释义 Definition

Kadane（通常指 Kadane’s algorithm，卡达内算法）：一种在 O(n) 时间内求解数组中“最大连续子数组和”（maximum subarray sum）的经典算法，常作为动态规划思想的入门例子。（在技术语境中更常见；作为姓氏时也可指人名。）

发音 Pronunciation (IPA)

/kden/

例句 Examples

Kadane’s algorithm finds the maximum subarray sum in linear time.
卡达内算法能在线性时间内找到最大连续子数组和。

When the input contains negative numbers, Kadane’s algorithm still works by updating the running best and the global best at each step.
当输入包含负数时，卡达内算法仍然有效，因为它会在每一步更新“当前最优”和“全局最优”。

词源 Etymology

“Kadane”来自算法命名：该线性时间解法通常被称为 Kadane’s algorithm，以提出/推广该思路的研究者 Jay Kadane 命名；后来在算法与竞赛编程社区中广泛传播，成为最大子数组问题的常用解法名称。

相关词 Related Words

• Maximum Subarray
• Dynamic Programming
• Subarray
• Prefix Sum
• Divide And Conquer
• Linear Time
• Time Complexity

文学与著作中的出现 Literary Works

• **Introduction to Algorithms (CLRS)**：在“最大子数组问题”中给出线性时间解法（常在教学与注释中与 Kadane 关联）。
• Competitive Programming（竞赛编程教材）（如 Steven & Felix Halim 的系列）：常直接以 “Kadane’s algorithm” 讲解最大子段和。
• The Algorithm Design Manual（Steven S. Skiena）：在数组/动态规划相关章节与题型讨论中常提及该问题与常用线性解法（实践中常称 Kadane）。