A day or two ago I was browsing Reddit.com and saw a question regarding finding the maximum sum of a sub array given an array of integers. I decided to do some exploration on the Kadane’s algorithm. I tried a couple brute force implementations. I then went for an implementation using the algorithm.
Maximum Subarray Sum Given an integer arry nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
The problem definition is quite simple. Implementing a brute force is not too bad but it is quite slow. After a couple implementations we will use Kadane’s algorithm in the third approach.
If interested in the Maximum Subarray problem you can read more about it in Wikipedia. To learn more about the Kadane’s algorithm you can also use Wikipedia. It seems that the problem and associated solution are popular topics.
1,2,3 main <<< nums: [1, 2, 3] main <<< bruteForce: 6 main <<< optimized: 6 main <<< kadanes: 6 -2,1,-3,4,-1,2,1,-5,4 main <<< nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4] main <<< bruteForce: 6 main <<< optimized: 6 main <<< kadanes: 6 -2,-3,4,-1,-2,1,5,-3 main <<< nums: [-2, -3, 4, -1, -2, 1, 5, -3] main <<< bruteForce: 7 main <<< optimized: 7 main <<< kadanes: 7 -2,2,5,-11,6 main <<< nums: [-2, 2, 5, -11, 6] main <<< bruteForce: 7 main <<< optimized: 7 main <<< kadanes: 7 1,2,3,-7,1,3,5 main <<< nums: [1, 2, 3, -7, 1, 3, 5] main <<< bruteForce: 9 main <<< optimized: 9 main <<< kadanes: 9 -7,1,2,3,-7,1,3,5 main <<< nums: [-7, 1, 2, 3, -7, 1, 3, 5] main <<< bruteForce: 9 main <<< optimized: 9 main <<< kadanes: 9
Our test scaffolding is presented with a line of integer values separated by ‘,’s. It appears that the program reads and parses the input data and generates an array. The array should be passed to our three implementations.
public int maxSubarraySum(int[] nums) {
}
The prototype for this problem implemented in Java would accept a single array of integers. It should return the value of the largest contiguous sub array. Note that since I am generating three solutions I decided to give them three different names.
/**
* Test scaffolding.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open stream ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read array ****
String[] numStrs = br.readLine().trim().split(",");
// **** close stream ****
br.close();
// **** populate nums array ****
int[] nums = new int[numStrs.length];
for (int i = 0; i < numStrs.length; i++) {
nums[i] = Integer.parseInt(numStrs[i]);
}
// ???? display array ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** find and display the max sum of a subarray ****
System.out.println("main <<< bruteForce: " + bruteForce(nums));
// **** find and display the max sum of a subarray ****
System.out.println("main <<< optimized: " + optimized(nums));
// **** find and display the max sum of a subarray ****
System.out.println("main <<< kadanes: " + kadanes(nums));
}
As we assumed, our code reads and parses the first and only input line. With the values we generate an integer array. The array is passed to the three implementations. The first two could be called brute force approaches. The third is the optimal solution implementing Kadane’s algorithm.
/**
* Brute force approach.
* O(n^3)
*/
static int bruteForce(int[] nums) {
// **** sanity check(s) ****
if (nums == null)
return 0;
if (nums.length == 1)
return nums[0];
// **** initialization ****
int maxSum = 0;
// **** from start ... O(n) *****
for (int s = 0; s < nums.length; s++) {
// **** ... to end ... O(n) ****
for (int e = s; e < nums.length; e++) {
// **** compute sum O(n) ****
int sum = 0;
for (int i = s; i <= e; i++) {
sum += nums[i];
}
// **** update max sum ****
maxSum = Math.max(maxSum, sum);
}
}
// **** return max sum ****
return maxSum;
}
What we need to do is generate all combinations and compute the sum of the sub arrays. We do so with three loops. The first one moves the starting index. The second loop sets the ending index. The third loop performs the sum of the elements and stores the largest value.
When done, we return the largest / maximum value.
The execution time is O(n^3) which is pretty bad for any algorithm that processes large number of values. Let’s skip it.
/**
* Optimized approach.
* O(n^2)
*/
static int optimized(int[] nums) {
// **** sanity check(s) ****
if (nums == null)
return 0;
if (nums.length == 1)
return nums[0];
// **** initialization ****
int maxSum = 0;
// **** from start ... O(n) *****
for (int s = 0; s < nums.length; s++) {
// **** ... to end ... O(n) ****
int sum = 0;
for (int e = s; e < nums.length; e++) {
// **** update sum ****
sum += nums[e];
// **** update max sum ****
maxSum = Math.max(maxSum, sum);
}
}
// **** return max sum ****
return maxSum;
}
This pass is a simple optimization based on the first solution. Instead of generate the sums on a third loop we compute and check inside the second one. I copied the previous code and made some changes. This solution is better but it is O(n^2) so we are not there yet.
/**
* Using Kadane's algorithm.
* Execution: O(n)
*/
static int kadanes(int[] nums) {
// **** sanity check(s) ****
if (nums == null)
return 0;
if (nums.length == 1)
return nums[0];
// **** initialization ****
int bestSum = Integer.MIN_VALUE;
int currSum = nums[0];
// **** traverse nums O(n) ****
for (int i = 1; i < nums.length; i++) {
// **** increment or restart / reset sum ****
currSum = Math.max(currSum + nums[i], nums[i]);
// **** update best sum if needed (remember best sum) ****
bestSum = Math.max(bestSum, currSum);
}
// **** return best sum ****
return bestSum;
}
In this approach we will use Kadane’s algorithm.
Note that the first couple statements implement some sanity checks. If the array is empty we can immediately return a value of 0. If the array contains a single value we can immediately return the single element in the array as the maximum.
We then perform initialization of tow variables. The first will be used to keep track of the best sum of elements in a sub array. The second will keep track of the sum of the current sub array.
We then loop through the elements in the array. Note that by initializing currSum to the first array element we can start traversing the array at element 1.
The loop contains two statements. First we increment or reset the current sum. If the current sum is larger than the current array value, we should use it as our current sum; otherwise we restart the sum with the value of the current array.
In the second statement inside the loop, we maintain the best sum. If the current sum is larger / better we replace the best sum with the current one.
Take a look at the examples and perform the loop by hand. It is simple, it works and it generates the proper results in O(n) execution time.
When done we return the value of the best sum.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 4,724 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
john.canessa@gmail.com