Arrays & Strings

Prefix sums and Kadane's max subarray

Arrays: Prefix Sum & Kadane's

Array
1
0
2
1
2
2
14
3
7
4
6
5
-1
6
0
7
10
8
7
9

Five-Stage Pipeline

1. Prefix Sum — The prefix sum array stores cumulative sums. Each element prefix[i] equals the sum of all elements from index 0 to i. This enables O(1) range sum queries.

2. Kadane's Algorithm — Finds the contiguous subarray with the largest sum in O(n) time. At each step, we decide: extend the current subarray or start fresh from the current element.

Complexity

Prefix Sum
Time:O(n)
Space:O(n)
Kadane's
Time:O(n)
Space:O(1)