Maximum Subarray (Kadane)
Find the contiguous subarray with the largest sum and return that sum.
Answers use simple, clear English.
Audio N/AQuick interview answer
Kadane's algorithm: keep best_ending_here = max(x, best_ending_here + x) and a global max. Handles all-negative arrays if you initialize carefully with the first element or -inf.
Detailed answer
Kadane's algorithm: keep best_ending_here = max(x, best_ending_here + x) and a global max. Handles all-negative arrays if you initialize carefully with the first element or -inf. Empty subarray allowed only if the problem says so (LeetCode 53 usually disallows empty).
Full explanation
Empty subarray allowed only if the problem says so (LeetCode 53 usually disallows empty).
Real example & use case
Detect the most profitable contiguous trading window inside an intraday PnL series.
Pros & cons
Pros: O(n)/O(1). Cons: only contiguous; non-contiguous needs different DP.
Code example
def max_sub_array(nums: list[int]) -> int:
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return bestPractice code · python (view only · no execution)
def max_sub_array(nums: list[int]) -> int:
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x)
best = max(best, cur)
return best