Remember
- Prefix sums cost O(n) once, then every range sum is two lookups and a subtraction.
- Kadane's rule: a negative run can only hurt whatever it touches, so drop it and start over.
- Both are one pass. If you find yourself summing the same slots twice, one of these applies.