最大子数组和与最大乘积子数组
将 Kadane 算法应用于最大和子数组问题，并扩展为同时跟踪最大值和最小值，以解决最大乘积变体。
最大子数组和与最大乘积子数组 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
最大和子数组问题
最大子数组问题要求您在一维数字数组中找出和最大的连续子数组。例如，在 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 中，子数组 [4, -1, 2, 1] 的和为 6，是最大和。暴力 O(n²) 方法会检查所有子数组，而卡丹算法可以在O(n) 时间内解决该问题。
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6卡丹算法直觉
卡丹算法只需遍历一次数组，同时维护一个不断累加的 current_sum。对于每个元素，您需要判断：是扩展现有子数组更好，还是从当前元素重新开始更好？如果 current_sum 变为负数，它只会损害之后的任何子数组，因此应重新开始。递推式为 current_sum = max(num, current_sum + num)。
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6跟踪卡丹算法
让我们跟踪卡丹算法在 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 上的执行过程：从 curr=-2、max=-2 开始。在 1 处：curr=max(1,-2+1)=1，max=1。在 -3 处：curr=max(-3,1-3)=-2，max=1。在 4 处：curr=max(4,-2+4)=4，max=4。在 -1 处：curr=3，max=4。在 2 处：curr=5，max=5。在 1 处：curr=6，max=6。在 -5 处：curr=1。在 4 处：curr=5，max=6。该算法正确识别出以索引 6 结尾的子数组是最优解。
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])返回实际子数组
如果面试官要求您返回子数组本身（而不仅仅是返回和），就需要跟踪起始索引和结束索引。当您重新开始时（因为 num > current_sum + num），请更新 temp_start。更新 max_sum 时，将 temp_start 保存为 start，并将当前索引保存为 end。这只会为同一个 O(n) 算法增加 O(1) 的额外开销。
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])最大乘积子数组问题
最大乘积子数组问题比求和版本更棘手，因为其中涉及负数。两个负数相乘会得到正数，因此，一个非常小的负乘积与另一个负数相乘后，可能变成最大乘积。对于 [2, 3, -2, 4]，答案是 6（[2, 3]）。对于 [-2, 0, -1]，答案是 0。我们必须在每一步同时跟踪最大乘积和最小乘积。
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)跟踪最大和最小乘积
关键洞察是：在每个位置，当前最大乘积可能是 num、max_so_far * num 或 min_so_far * num 之一（最后一种情况会在负数将最小值反转为最大值时发挥作用）。最小乘积的情况也类似。请使用之前的值同时更新 cur_max 和 cur_min，以避免在同一步中使用已经更新过的值。
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2最小乘积为何重要
考虑 [-3, -10, 5]。处理 -3 后：max=-3，min=-3。处理 -10 后：候选值为 (-10, 30, 30) → max=30，min=-10。处理 5 后：候选值为 (5, 150, -50) → max=150。如果不跟踪 min_prod，就会错过大负数最小值与另一个负数相乘时发生的反转。请始终根据同一组之前的值计算最大值和最小值，以避免陈旧读取错误。
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 150零会重置乘积
数组中的零会将两个累计乘积都重置为零，从而有效地把数组分割成相互独立的子数组。当 num = 0 时，max_prod * 0 = 0 和 min_prod * 0 = 0，因此三个候选值都会变为 0，同时保留之前的最大结果。无需编写特殊情况代码——通用公式会自然处理零值。
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0另一种方法：左右乘积扫描
另一种方法是从左向右和从右向左扫描，并在遇到零时将累计乘积重置为 1。最大乘积子数组绝不会跨过零，因此，如果负数使某个方向的结果变差，反向扫描就会捕捉到这次反转。这种方法很简洁，但在面试中更常被期待使用的是最小值/最大值跟踪方法。
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0卡丹算法与乘积：关键区别
和子数组与乘积子数组存在重要差异。对于求和：负数总是有害的，因此应采用贪心策略重新开始。对于求积：两个负数会带来帮助，因此必须同时跟踪两端的极值。此外，零对乘积而言会终止当前计算，但对和而言只会造成轻微影响。在面试中进行讲解时，请明确指出这些差异，并在编写代码前解释为什么必须跟踪最小值。
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24复杂度与面试技巧
卡丹算法（最大和）和最小值/最大值跟踪方法（最大乘积）的运行时间都是O(n)，空间复杂度都是O(1)。面试技巧：(1) 对于最大和，请提到 O(n log n) 的分治替代方案，以展示您掌握多种方法。(2) 对于最大乘积，请强调要根据之前的值同时更新 min_prod 和 max_prod，以避免使用陈旧数据。(3) 请始终确认：数组可以为空吗？子数组必须非空吗？（是的，按照惯例，子数组必须非空。）
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negative快速检查
请检验您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学到了：卡丹算法通过在每个元素处选择扩展或重新开始，在 O(n) 时间内解决最大和子数组问题、由于负数会发生反转，最大乘积子数组需要同时跟踪最小和最大的累计乘积，以及零会自然地重置累计乘积，无需特殊情况代码。接下来，我们将使用一维 DP 表探索单词拆分问题。
常见问题解答
「最大子数组和与最大乘积子数组」课时是免费的吗？
是的 — 「最大子数组和与最大乘积子数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「最大子数组和与最大乘积子数组」这节课中我会学到什么？
将 Kadane 算法应用于最大和子数组问题，并扩展为同时跟踪最大值和最小值，以解决最大乘积变体。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「最大子数组和与最大乘积子数组」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 打家劫舍：选择或跳过的递推
- 最大子数组和与最大乘积子数组
- 单词拆分与字符串分段
- 解码方法与路径计数