Maximum Subarray Sum

Go to:
> Material
> Lecture Recap

Material

• Slides: pre-class (w.o. solutions)
• Slides: with solutions & annotations (after class)

Lecture Recap

This week you saw the maximum subarray problem, a classic challenge that asks for the subarray with the largest possible sum. We looked at a few different ways to solve it, starting with a couple of brute-force methods to get a sense of the problem, then moving on to a divide-and-conquer approach that uses recursion to work smarter, not harder. Finally we saw our first dynamic programming solution that solves the problem in one pass. The main goal was to see how different strategies can tackle the same problem and to practice figuring out how their runtimes and efficiencies compare.