Prefix Sums & Kadane's Algorithm — Subarray Math

Subarray-sum questions have two power tools. Both turn repeated O(n) summing into O(1) lookups.

Prefix sums — precompute once, answer forever

// prefix[i] = sum of nums[0..i-1]
const prefix = [0];
for (const x of nums) prefix.push(prefix[prefix.length - 1] + x);

// sum of any range [i..j] in O(1):
const rangeSum = prefix[j + 1] - prefix[i];

One O(n) pass buys unlimited O(1) range queries. The famous level-up: "count subarrays summing to K" = prefix sums + the hashmap pattern — for each prefix, ask "have I seen prefix − K before?" Two patterns chained again.

Kadane's — maximum subarray in one pass

function maxSubArray(nums) {
  let cur = nums[0], best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur  = Math.max(nums[i], cur + nums[i]);  // extend, or start fresh here?
    best = Math.max(best, cur);
  }
  return best;
}

The one-line insight: at each element, the best subarray ending here either extends the previous best or starts fresh — whichever is larger. A negative running sum can only hurt, so you drop it. This is actually a tiny dynamic program, which makes it a perfect DP warm-up.

Spot it when…

• "Sum of subarray/range" asked many times → prefix sums.
• "Maximum/minimum subarray sum" → Kadane's.
• "Subarray sum equals/divisible by K" → prefix + hashmap.

Practice now

• Maximum Subarray (Kadane) — with hidden all-negatives test, the classic trap
• Product of Array Except Self — the same prefix idea applied with multiplication