Scenario
Create an algorithm to solve the maximum subarray problem. Find the non-empty, contiguous subarray of the input array whose values have the largest sum. You can see an example array with the maximum subarray indicated in the following diagram:
The O(n2) brute force algorithm that tests all combinations for the start and end indices of the subarray is trivial to implement. Try to solve this using the divide and conquer algorithm.
Aim
To design and implement an algorithm to solve the maximum subarray problem with a better runtime than the O(n2) brute force algorithm, using a divide and conquer approach.
Prerequisites
- You need to implement the maxSubarray() method of the MaximumSubarray class in the source code, which returns the sum of values for the maximum subarray of the input array. The code is available on the following path:
https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson4/activity/maxsubarray/MaximumSubarray.java - Assume that the sum always fits in an int, and that the size of the input array is at most 100,000.
Steps for Completion
The divide and conquer approach suggests that we divide the subarray into two subarrays of as equal size as possible. After doing so, we know that a maximum subarray must lie in exactly one of following three places:
- Entirely in the left subarray
- Entirely in the right subarray
- Crossing the midpoint
The maximum subarray of the arrays on the left and right is given recursively, since those subproblems are smaller instances of the original problem.
Find a maximum subarray that crosses the midpoint.
There exists an even faster dynamic programming algorithm with a runtime of O(n) to solve the maximum subarray problem. The algorithm is called Kadane's algorithm. Dynamic programming will be explored in the next section.
In the second section, we introduced the divide and conquer paradigm of algorithm design. We formalized the steps that a divide and conquer algorithm goes through, and showed the students how to go from a recurrence relationship to a runtime complexity bound using the master theorem. To gain intuition about the applicability of divide and conquer algorithms, we explored the problem of finding the closest pair of points on a plane.