Greedy

LeetCode 53

LeetCode #53Difficulty: MediumNeetCode 150

LeetCode 53: Maximum Subarray (Kadane's Algorithm)

LeetCode

Find the subarray with the largest sum, and return its sum.

Problem Description

Given an integer array `nums`, find the subarray with the largest sum, and return its sum.

Examples:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6

Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Constraints:
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Core Mental Model

Maintain runningSum. If runningSum drops below 0, carrying it into future numbers only reduces their sum! Discard the negative prefix and restart from 0.

Formal Loop Invariant

Invariant: maxSubarraySum ends at or before current index; negative prefixes are strictly discarded.

Key Architectural Takeaway:

A negative prefix can never contribute to a maximal subsequent subarray sum.

Asymptotic Complexity Analysis

Time ComplexityO(N) single passLinear scan
Space ComplexityO(1) scalars.Constant auxiliary

Bottleneck: Linear scan.

Edge Cases & Screener Traps

  • All negative numbers: [-3, -2, -5] -> max is -2