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 problem faster. Consider the situation where we divide our input array exactly in half. Let’s call the array A and say that the first index in the array is low and the last index is high. The optimal subarray could exist in three different locations when we split in half:
1. Entirely in the first half of the array, A[low:mid]
2. Entirely in the second half of the array, A[mid+1:high]
3. Crossing the midpoint, so that it starts in the first half of the array, and ends in the second half of the array
From this, we can recursively the maximum subarray of the first half and second half of the array. If we are able to do this, we can find the maximum subarray crossing the midpoint in linear time. To do this, we would use the following algorithm.