算法核心思想
我们可以从两个角度理解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
