Dynamic Programming And Mutable Range Queries

What's being tested

This tests dynamic programming, contiguous subarray optimization, and mutable range-query data structures under interview constraints. You need to recognize when a problem is a one-pass recurrence, a memoized state transition, or a data structure API such as `update(row, col, val)` plus `sumRegion(r1, c1, r2, c2)`.

Patterns & templates

• Kadane’s algorithm for maximum subarray sum — track bestEndingHere and bestSoFar; O(n) time, O(1) space.

• Maximum product subarray — track both maxEndingHere and minEndingHere; negatives swap roles, zeros reset naturally.

• Top-down DP with memoization — define dp(i, state) before coding; cache with array/map; prove transitions cover all legal choices.

• Bottom-up DP with rolling arrays — convert recurrence to iteration; reduce space from O(nk) to O(k) when only previous row matters.

• Solution reconstruction — store parent[i][state] or recompute choices from dp; do not optimize away information if output path is required.

• 2D Fenwick tree / Binary Indexed Tree — point update and rectangle sum in O(log m log n) using inclusion-exclusion over prefix sums.

• 2D segment tree alternative — supports richer operations but is harder to implement; usually only choose it if updates/queries are not simple sums.

Common pitfalls

Pitfall: Using a static prefix-sum matrix for mutable queries gives O(1) reads but O(mn) updates, which fails dynamic-update constraints.

Pitfall: For maximum product subarray, tracking only the maximum misses cases where a large negative becomes optimal after multiplying by another negative.

Pitfall: In DP color-assignment problems, forgetting the “adjacent colors differ” constraint in the state transition produces locally cheap but invalid assignments.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.