17370845950

算法核心思想

我们可以从两个角度理解Kadane算法的核心：

算法步骤

算法使用两个变量：maxSum 和 maxTillNow。

• maxSum：记录遍历过程中遇到的最大子数组和。
• maxTillNow：记录当前遍历位置为止的最大子数组和。 maxTillNow 会随着遍历不断更新，当遇到负数时可能变小，但 maxSum 始终保持最大值。

算法遍历数组：

1. 初始化 maxSum 为负无穷大，maxTillNow 为 0。
2. 遍历数组元素，将当前元素加到 maxTillNow 中。
3. 如果 maxTillNow 大于 maxSum，则更新 maxSum。
4. 如果 maxTillNow 小于 0，则将其重置为 0，表示从下一个元素开始重新计算子数组和。

算法复杂度

• 时间复杂度: O(n)，因为算法只遍历数组一次。
• 空间复杂度: O(1)，因为算法只使用了常数个额外变量。

代码实现

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int maxTillNow = 0;
        for (int i = 0; i < nums.length; i++) {
            maxTillNow += nums[i];
            maxSum = Math.max(maxTillNow, maxSum);
            if (maxTillNow < 0) {
                maxTillNow = 0;
            }
        }
        return maxSum;
    }
}

更多算法解决方案，请访问我的https://www./link/19c768e48aca9308d1a11fe86157731fHub仓库：https://www./link/19c768e48aca9308d1a11fe86157731fHub链接 LeetCode用户名：devn007