Maximum Subarray Problem Using Brute Force, Divide And Conquer

In this blog post you would learn

• Very interesting example of maximum subarray problem
• Discuss the algorithm, pseudocode, analyze the complexity and write a program related to solving maximum subarray problem using brute force technique
• Discuss the algorithm, pseudocode, analyze the complexity and write a program related to solving maximum subarray problem using divide and conquer algorithm

Suppose you are working in a firm that analyzes the behavior of bitcoin in last 10 hours and you are assigned a task to check what would have been the right time to invest and right time to withdraw your bitcoins to have the maximum profit. Of course you want to “buy low , sell high”. You want to buy at the lowest price and sell at the highest price in order to maximize the profit. However, that’s not always the case. Let us consider the following example.

In the above graph x-axis shows dates and y-axis shows price of bitcoin.

In the above table we show the date, price and change of price of bitcoin. We see that even though the minimum price of bitcoin is on 25^th Feb and maximum price of bitcoin is on 22^nd Feb, however in order to maximize the profit, one should buy the stock on 23^rd Feb and sell it on 24^th Feb which is neither the highest nor the lowest price.

Brute-Force Approach

If we try each and every possible combination to find the maximum subarray, we can find the maximum subarray. Like taking the array with 1 size, then taking 2 size subarray and then till n size subarray. If we consider the above table and take the change values tuples only, we can find the maximum subarray. Let us consider the following algorithm

Analyzing the complexity of the above algorithm

The complexity of the above algorithm is bigO of n^3. Since the inner most loop has to be executed n^3 times in order to complete the execution. This type of algorithm, even though it solves the problem, is not very efficient. We’ll look at a more efficient approach using divide and conquer.

Divide and conquer Approach

Divide and conquer suggests that we divide the array into two equal subarrays of equal size as possible. Suppose we have array of A[low…high], which is divided into A[low…mid] and A[mid+1…high].In order for any contiguous subarray, it must lie in the following places:

Left part of subarray A[low…mid]

Right part of subarray A[mid+1…high]

Middle part of subarray A[low…high]

We can easily find a maximum subarray crossing the midpoint in linear time in the size of subarray A[low..high]. This problem is not a smaller instance of our original problem, because it has an added restriction that it must cross the midpoint. Once we find the maximum subarray all we need to do is to combine the array. In the pseudocode below

In the pseudocode we are given a function Maximum-mid-crossing-subarray which takes an array A, mid, low and high values that determines the max sum in the left, right and mid crossing of the array.

The procedure works as follows. Line number 20-25 determines the maximum subarray on the right side subarray and line number 27-32 determines the maximum subarray on the left side of subarray. Finally, line 34 returns max left index, max right index and sum crossing the mid of subarray.

We write another function called Maximum-subarray in pseudocode, in line 3-4 we write the base case of the function. If the array has only one element, then the array bottoms out and hits the base case of the array. Line number 6-9 divides the algorithm into subparts. Line number 10-15 combines the subarray and determines whether left subarray or right subarray or if the maximum subarray crosses the middle part of the array.

Analyzing divide and conquer algorithm

As we did when we analyzed merge sort here, we made the assumption that the original problem size is a power of 2, so that all subproblem sizes are integers. We donate by T(n) the running time of Maximum-subarray on a subarray of n numbers. When we hit the base case it is time constant and reached in

T(n) = theta (1)

Each of subproblem from line 7-9 is of size n/2 (since array is divided into 2 equal parts), so we spend T(n/2) time solving each of them. Since we solve right and left subarray we have 2T(n/2). Maximum-mid-crossing-subarray takes theta(n) time. For the recursive case we have

T(n) = theta(1)    if n=1

2T(n/2) + theta(n) if n>1

The recurrence is same for merge sort and this recurrence has a solution of T(n) = theta(n lgn), where lg is log base 2.

Thus, we see that the divide and conquer approach yields a more efficient solution than brute force approach.

Program for maximum subarray using brute force method can be found here

Program for maximum subarray using divide and conquer can be found here

That’s all for now! We looked at solving maximum subarray problem using brute force which would solve in theta(n^3) time and solved maximum subarray problem using divide and conquer approach in theta(n lgn) time. Next we will try to solve the problem in theta(n) time.