DATA STRUCTURES › ARRAYS

Maximum Subarray Sum

Find the contiguous subarray with the largest sum. This is the problem statement behind Kadane's algorithm and one of the most important array-to-DP bridges.

Time

O(N)

Space

O(1)

Key Principle 1

Track the best sum ending at the current index.

Key Principle 2

If the running sum becomes negative, restart from the current value.

Key Principle 3

Negative numbers are part of the problem, not a special case to avoid.

Key Principle 4

This pattern appears in profit, scoring, and signal-processing problems.

Loading Lab...