含正负值任意长度两不重叠子数组最大和解法咨询

问题背景 #

• 固定长度、元素全为正数的两不重叠子数组最大和为经典算法题，在主流刷题平台均有收录。
• 本次讨论的变种问题规则为：子数组长度无限制，数组元素同时包含正负数，目标是找到两个不重叠的子数组，使得二者的元素和相加最大。
• 提问者自拟了一套解法，在部分自造测试用例上运行结果符合预期，但存在三点待解答疑问。

提问者自拟解法逻辑 #

1. 构建名为maxSumAtIndex的数组，参照Kadane算法逻辑填充每个索引值：若前一索引存储值加当前原数组值大于当前原数组值，则存入该和，否则直接存入当前原数组值。
2. 找到maxSumAtIndex中最大值对应索引（示例为索引10），从该索引向数组起始端回溯找到次大值对应索引（示例为索引7），原数组两索引区间内的元素和即为第一个子数组的和。
3. 第二个子数组必然位于第一个子数组的左侧或右侧区间，找到两个区间中maxSumAtIndex的最大值对应索引（示例为索引18），从该索引向所在区间起始端回溯找到区间内次大值对应索引（示例为索引12），原数组两索引区间内的元素和即为第二个子数组的和。
4. 将两个子数组的和相加得到最终结果finalSum。

自造测试用例：原数组为[-9,5,-9,-8,9,7,-10,10,9]，预期正确结果为35；对应生成的maxSumAtIndex数组为[-9,5,-4,-8,9,16,6,16,25]，按上述解法计算得到两子数组和为19、16，相加得35，结果符合预期。

疑问解答 #

1. 收录该变种题的刷题平台 #

目前国内主流刷题平台包括牛客网、AcWing均收录了该变种题目，题名多为「两个不重叠子数组的最大和」；海外刷题社区也有同类型题目收录，使用关键词maximum sum of two non-overlapping subarrays即可检索到对应题目。

2. 自拟解法的正确性判定 #

该解法不成立，无法覆盖所有测试场景，核心逻辑漏洞有两点：

• 子数组区间回溯规则错误：maxSumAtIndex数组本质是Kadane算法的中间数组，每个位置存储的是以当前索引为结尾的最大子数组和，对应子数组的真实起点是往回遍历到的第一个满足maxSumAtIndex[k] == nums[k]的位置（即子数组和的增益起始点），而非“次大值对应索引”。比如测试用例[2, -3, 1, 2, -3, 2]，按该回溯规则会得到错误的子数组区间，计算结果为4，实际正确结果为5。
• 贪心选择前提错误：解法默认“最优解一定包含全局最大子数组”，这个前提不成立。存在全局最大子数组被负数拖累，拆分为两个不重叠子数组后总和更大的场景。比如测试用例[3, -2, 3, -2, 3]，全局最大子数组为整个数组，和为5，按该解法逻辑最终结果为5，但实际最优解是取第一个3和最后一个3，总和为6，明显优于计算结果。
  部分自造用例运行正确只是刚好契合逻辑，不代表解法具备普适正确性。

3. 最优解法说明 #

该问题存在时间复杂度O(n)、空间复杂度O(n)（可优化至O(1)）的最优解法，为该问题的标准解法，思路如下：

• 第一步：从左到右遍历数组，用Kadane算法计算leftMax数组，leftMax[i]表示数组前i个元素（即区间[0,i]）内的最大子数组和。
• 第二步：从右到左遍历数组，用Kadane算法计算rightMax数组，rightMax[i]表示数组从i到末尾（即区间[i, n-1]）内的最大子数组和。
• 第三步：遍历所有可能的分割点k（k从0到n-2），计算leftMax[k] + rightMax[k+1]，所有计算结果中的最大值即为最终答案。
  该解法核心原理非常直白：任意两个不重叠的子数组，必然存在一个分割点，使得第一个子数组完全在分割点左侧，第二个子数组完全在分割点右侧，因此遍历所有分割点取最大值即可覆盖所有可能的最优场景，无冗余计算，复杂度已经达到理论下界。

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