Maximum Subarray Algorithm Basic Information
Maximum subarray problem is the method to find the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
The problem was originally proposed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images.
We can problem like this, let us consider a list of various integers. We might be interested in which completely adjacent subset will have the greatest sum. For example, if we have the array
[0, 1, 2, -2, 3, 2], the maximum subarray is
[3, 2], with a sum of
Brute-Force Approach for Solution:
This method is most inefficient to find out the solution. In this, we will end up going through every single possible subarray, and then finding the sum of all of them. At last, compare all values and find out maximum subarray.
Pseudo code for Brute-Force Approach:
MaxSubarray(array) maximum = 0 for i in input current = 0 for j in input current += array[j] if current > maximum maximum = current return maximum
Time complexity for Brute-Force method is
O(n^2). So let’s move to divide and conquer approach.
Divide and Conquer Approach for Solution:
Find the sum of the subarrays on the left side, the subarrays on the right. Then, take a look through all of the ones that cross over the center divide, and finally return the maximum sum. Because this is a divide and conquer algorithm, we need to have two different functions.
First is divide step,
maxSubarray(array) if start = end return array[start] else middle = (start + end) / 2 return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))
In second part, separate the different part that are created in first part.
maxCrossover(array) currentLeftSum = 0 leftSum = 0 currentRightSum = 0 rightSum = 0 for i in array currentLeftSum += array[i] if currentLeftSum > leftSum leftSum = currentLeftSum for i in array currentRightSum += array[i] if currentRightSum > rightSum rightSum = currentRightSum return leftSum + rightSum
Time complexity for Divide and Conquer method is
O(nlogn). So let’s move to dynamic programming approach.
Dynamic Programming Approach:
This solution is also known as Kadane’s Algorithm. It is linear time algorithm. This solution is given by Joseph B. Kadane in late ’70s.
This algorithm just goes through the loop, continuously changing the current maximum sum. Interestingly enough, this is a very simple example of a dynamic programming algorithm, since it takes an overlapping problem and reduces it so we can find a more efficient solution.
Pseudo code of Kadane’s Algorithm:
MaxSubArray(array) max = 0 currentMax = 0 for i in array currentMax += array[i] if currentMax < 0 currentMax = 0 if max < currentMax max = currentMax return max
Time complexity for Kadane’s Algorithm is