1 / 4思路
Maximum Subarray
思路
Kadane 算法:current 表示“以当前元素结尾的最大子数组和”。如果 current 变成负数,加上后面的元素只会更小,于是从当前元素重新开始。best 记录全局最大值。
复杂度
- 时间 O(n):一次遍历。
- 空间 O(1):只维护两个变量。
代码
- Python
- TypeScript
def max_sub_array(nums: list[int]) -> int:
current = best = nums[0]
for value in nums[1:]:
current = max(value, current + value)
best = max(best, current)
return best
function maxSubArray(nums: number[]): number {
let current = nums[0];
let best = nums[0];
for (let index = 1; index < nums.length; index += 1) {
current = Math.max(nums[index], current + nums[index]);
best = Math.max(best, current);
}
return best;
}
边界
- 全为负数:返回最大的单个元素,不能返回 0。
- 只有一个元素:直接返回它。
- 空数组:题目保证非空;工程代码应显式处理。