> For the complete documentation index, see [llms.txt](https://docs.ramsdenj.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.ramsdenj.com/introduction-4/notes/dp.md).

# DP

## Kadane's Algorithm

Can be used to find the maximum sum of a subarray.

Basically store in a variable, the best sum ending at an index. This will either be the best sum at the last index plus the current value, or it will be the current value. So if the previous best does not improve by adding the current, we will essentially reset.