LeetCode 918题逻辑困惑：环形数组最大子数组和相关疑问

问题回顾 #

给定环形整数数组nums，求非空子数组的最大可能和。环形数组意味着数组首尾相连，子数组不能重复包含元素。

核心逻辑拆解 #

环形数组的最大子数组和只有两种可能场景：

• 场景1：子数组不跨首尾：这就是普通数组的最大子数组和问题，直接用Kadane算法求解即可。
• 场景2：子数组跨首尾：比如子数组由数组末尾的一段 + 开头的一段组成，此时它的互补部分是数组中间连续的一段子数组（记为A），而目标子数组（记为B）的和 = 数组总和total_sum - 子数组A的和sum(A)。

为什么A必须是最小和子数组？ #

因为total_sum是固定值，要让sum(B)最大，就必须让sum(A)尽可能小——这是减法的基本逻辑：被减数固定时，减数越小，结果越大。

如果选一个和介于中间的子数组A'，那么total_sum - sum(A')必然小于total_sum - sum(A)（其中A是最小和子数组），对应的B'的和也就不是场景2下的最大值。只有当A是数组的最小和子数组时，才能得到跨首尾场景下的最大子数组和。

特殊情况处理 #

如果数组所有元素都是负数，此时total_sum - sum(A)（A为整个数组，sum(A)=total_sum）的结果是0，但实际最大子数组应该是数组中最大的单个元素（因为所有子数组的和都是负数，选最大的那个）。因此最终答案需要取场景1的最大和与场景2的最大和中的较大值，这种情况下场景1的结果会自动覆盖场景2的无效值。

内容的提问来源于stack exchange，提问作者Anuttar