Objective: The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum.
Example: int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4}; Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Approach:
Naive solution would be use two for loops and check every subarray and return the subarray which has the maximum sum.
Time Complexity: O(N2)
Can we reduce it??? Yes, there are multiple solutions which solves this problem in O(N). In this article we will see very known algorithm called kadane’s Algorithm.
Click here to read about how to solve this problem using Dynamic Programming.
Kadane’s Algorithm:
start: max_so_far = 0 max_ending_here = 0 loop i= 0 to n (i) max_ending_here = max_ending_here + a[i] (ii) if(max_ending_here < 0) max_ending_here = 0 (iii) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far
Let’s walk through this algorithm with one example
int [] A = {−2, 1, −3, 4, −1, 2, 1};
max_so_far = 0 max_ending_here = 0 i=0 and a[0] = -2 max_ending_here = max_ending_here + (-2) = -2 max_ending_here < 0 => max_ending_here = 0 i=1 and a[1] = 1 max_ending_here = max_ending_here + (1) => 0 + 1 => 1 max_ending_here > 0 max_so_far < max_ending_here is true => max_so_far = max_ending_here max_so_far = 1 i=2 and a[2] = -3 max_ending_here = max_ending_here + (-3) => 1 -3 = -2 max_ending_here < 0 => max_ending_here = 0 max_so_far < max_ending_here is false so do not update max_so_far. max_so_far = 1 i=3 and a[3] = 4 max_ending_here = max_ending_here + 4 => 0 + 4 => 4 max_ending_here > 0 max_so_far < max_ending_here is true => max_so_far = max_ending_here max_so_far = 4 i=4 and a[4] = -1 max_ending_here = max_ending_here + (-1) => 4 - 1 => 3 max_ending_here > 0 max_so_far < max_ending_here is false max_so_far = 4 i=5 and a[5] = 2 max_ending_here = max_ending_here + 2 => 3 + 2 => 5 max_ending_here > 0 max_so_far < max_ending_here is true => max_so_far = max_ending_here max_so_far = 5 i=6 and a[6] = 1 max_ending_here = max_ending_here + 1 => 5 + 1 => 6 max_ending_here > 0 max_so_far < max_ending_here is true => max_so_far = max_ending_here max_so_far = 6 return max_so_far = 6
NOTE: The above algorithm works only when there is at least one positive element in the array.
We need to modify the algorithm to work it if all the elements are negative.
start: max_so_far = a[0] max_ending_here = a[0] loop i= 1 to n (i) max_end_here = Max(arrA[i], max_end_here+a[i]); (ii) max_so_far = Max(max_so_far,max_end_here); return max_so_far
Complete Code for both algorithms:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class MaximumSubArray { | |
// Kadane algorithm | |
public int kandane(int[] arrA) { | |
int max_end_here = 0; | |
int max_so_far = 0; | |
for (int i = 0; i < arrA.length; i++) { | |
max_end_here += arrA[i]; | |
if (max_end_here < 0) { | |
max_end_here = 0; | |
} | |
if (max_so_far < max_end_here) { | |
max_so_far = max_end_here; | |
} | |
} | |
return max_so_far; | |
} | |
// Below modification will allow the program to work even if all the | |
// elements in the array are negative | |
public int KandaneModify(int[] arrA) { | |
int max_end_here = arrA[0]; | |
int max_so_far = arrA[0]; | |
for(int i=1;i<arrA.length;i++){ | |
max_end_here = Math.max(arrA[i], max_end_here+arrA[i]); | |
max_so_far = Math.max(max_so_far,max_end_here); | |
} | |
return max_so_far; | |
} | |
public static void main(String args[]) { | |
int arrA[] = { 1, 2, –3, –4, 2, 7, –2, 3 }; | |
MaximumSubArray i = new MaximumSubArray(); | |
System.out.println("Maximum subarray is " + i.kandane(arrA)); | |
int arrB[] = { –2, –3, –4, –2, –7, –2, –3,–11 }; | |
System.out.println("Maximum Subarray when all elements are negative : " + i.KandaneModify(arrB)); | |
} | |
} | |
Output:
Maximum subarray is 10 Maximum Subarray when all elements are negative : -2
References:
https://en.wikipedia.org/wiki/Maximum_subarray_problem
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/