Member-only story
Solving the Maximum Subarray Problem with Divide and Conquer
Problem: Suppose you are able to invest in a company, under the condition that you can only buy once, and sell once. At the time of purchase, you are told the price of the stock for the coming week, so you can predict what the price will be a week into the future. You want to determine what the maximum profit you can make is.
As an example, suppose that the price of a stock is represented by the following list: [100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97]. If we wanted to find the maximum profit, we need to find the difference between two points that is largest. Your first intuitive idea may be to attempt a brute force type solution like below.
This solution works, in the sense that it gives the correct answer, however when studying algorithms, the idea of a solution changes. We not only want the correct answer, but we also want the correct answer in the fastest time possible. If you consider the time complexity of this algorithm, you will see that the outer most loop runs n times, and the inner most loop iterates i+1 — len(array) times. The general time complexity will be O(n²), which isn’t too bad, but can still be improved using divide and conquer.
When we want to design a divide and conquer algorithm, we need to divide the input in some way that helps us solve the…
