JS实现二维数组最大和子矩阵代码Kadane部分min逻辑的作用疑问

前置背景：二维问题降维到一维 #

代码的两层外层循环已经把二维求最大子矩阵的问题做了降维：

• 固定子矩阵的上边界i和下边界j
• 对每一列，计算从第i行到第j行的元素累加值，得到一个长度等于矩阵列数的一维数组
  此时问题就转化为：在这个一维数组中，找到连续子数组的最大和，你疑惑的几行代码就是经典Kadane算法的核心实现部分。

核心逻辑逐行解释 #

遍历一维数组时，temp是实时维护的数组前缀和：遍历到第k列时，temp的值等于一维数组从第0位到第k位的所有元素的和。

对于任意连续子数组的和，都可以拆解为两个前缀和的差值：假设子数组从第a位到第b位，它的和 = 前缀和[b] - 前缀和[a-1]；如果a=0，则子数组和直接等于前缀和[b]。

要让上述差值最大，对于当前遍历到的位置k（当前前缀和为temp），只需要找到之前所有位置出现过的前缀和最小值，用当前temp减去这个最小值，就能得到以k结尾的所有连续子数组中的最大和。
对应两行判断的具体作用：

• if (temp < min) { min = temp; }
  每计算得到一个新的前缀和temp，就更新历史前缀和的最小值。变量min的初始值设为0，刚好对应“从数组第0位开始计算、没有更早前缀和”的边界情况。
• if (temp - min > maxSum) { maxSum = temp - min; }
  用当前前缀和减去历史最小前缀和，得到以当前位置结尾的最大可能子数组和，再和全局记录的最大和maxSum比较，更新全局最大值。

为什么删除这段逻辑会得到错误结果 #

如果去掉这段逻辑，你维护的temp只是从数组开头一路累加的和，完全没有考虑“从数组中间某个位置开始的子数组，和可能远大于从头累加的和”的情况。
举个一维数组的实际例子：数组[-2, 1, -3, 4, -1, 2, 1, -5, 4]的最大和连续子数组为[4, -1, 2, 1]，对应和为6。
如果只用temp做累加判断：

• 累加得到的temp序列为：-2, -1, -4, 0, -1, 1, 2, -3, 1
• 最终能拿到的最大值只有2，和真实结果6偏差极大。
  加上min的逻辑后，才能正确捕获到中间段的高和子数组，得到正确结果。

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