Maximum Subarray Sum problem

I had to write down an example and work through it to figure this out. Here are my resulting whiteboard notes:

A few different implementations can be found here:

I think Kadane’s algorithm can also be used to solve the problem of finding the maximum profit from buying and selling shares from an array of daily prices:

I think we can calculate the differences between the daily prices and then treat this as a maximum subarray problem. So when the share price goes down and the total goes below zero, we reset this by setting the count to zero.

This entry was posted in programming and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.