leetExpert
Practice

Maximum Subarray (Kadane's Algorithm)

Module 12 · Prefix Sum

Problem

Given an integer array nums (may contain negatives), find the contiguous subarray with the largest sum, and return that sum.

Examples

Example 1

Inputnums = [-2,1,-3,4,-1,2,1,-5,4]Output6

Explanation. [4,-1,2,1]

Example 2

Inputnums = [1]Output1

Example 3

Inputnums = [5,4,-1,7,8]Output23

Explanation. the whole array

Constraints

1 ≤ n ≤ 10⁵ · values in ±10⁴.

Attempt it first

This is the module's capstone — and it's actually a problem you've already solved once. Best Time to Buy & Sell Stock (Module 4) tracked a running minimum and a running best profit in a single pass. This problem asks something structurally identical, phrased differently: find the connection before opening any hints.