Kadane 算法：Leetcode 最大子数组

wufei123 2025-01-26 阅读:1 评论:0

算法核心思想我们可以从两个角度理解Kadane算法的核心：算法步骤算法使用两个变量：maxSum 和 maxTillNow。 maxSum：记录遍历过程中遇到的最大子数组和。 maxTillNow：记录当前遍历位置为止的最大子数组...

kadane 算法：leetcode 最大子数组

算法核心思想

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

算法步骤

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

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

算法遍历数组：

初始化 maxSum 为负无穷大，maxTillNow 为 0。
遍历数组元素，将当前元素加到 maxTillNow 中。
如果 maxTillNow 大于 maxSum，则更新 maxSum。
如果 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.php.cn/link/19c768e48aca9308d1a11fe86157731fHub仓库：https://www.php.cn/link/19c768e48aca9308d1a11fe86157731fHub链接 LeetCode用户名：devn007

以上就是Kadane 算法：Leetcode 最大子数组的详细内容，更多请关注知识资源分享宝库其它相关文章！