Maximum Subarray
Given an integer array `nums`, find the contiguous subarray (containing at least one number) with the largest sum and return that sum. **Core Insight:** This is Kadane's Algorithm. The key observation is: at each position, we decide whether to extend the current subarray or start a fresh one. If the running sum becomes negative, it can only hurt any future subarray — so we reset it to 0 (or to the current element). We keep a global `maxSum` updated at every step. **Algorithm:** Initialize `maxSum = nums[0]` and `currentSum = 0`. For each number: add it to `currentSum`, update `maxSum = max(maxSum, currentSum)`, then if `currentSum < 0` reset it to 0. **Why it works:** A negative prefix sum is always worse than starting fresh. By discarding it, we guarantee the running sum represents the best subarray ending at the current position. **Complexity:** Time O(n) — single pass. Space O(1) — two variables.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-10⁴ ≤ nums[i] ≤ 10⁴
def maxSubArray(nums: list[int]) -> int:
max_sum = nums[0]
curr_sum = nums[0]
for num in nums[1:]:
curr_sum = max(num, curr_sum + num)
max_sum = max(max_sum, curr_sum)
return max_sum