Max Contiguous Subarray Sum

We cover the problem of finding the maximum contiguous subarray sum of a given sequence.

Table of Contents
Enroll in our 5-day mini coding interview class

Code Sample

/*
Maximum Subarray - LeetCode: https://leetcode.com/problems/maximum-subarray/
The video to explain this code is here: https://www.youtube.com/watch?v=2MmGzdiKR9Y
*/
/*
Time Limit Exceeded.
*/
class CubicTimeSolution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int maximumSubArraySum = Integer.MIN_VALUE;
/*
We will use these outer 2 for loops to investigate all
windows of the array.
We plant at each 'left' value and explore every
'right' value from that 'left' planting.
These are our bounds for the window we will investigate.
*/
for (int left = 0; left < n; left++) {
for (int right = left; right < n; right++) {
/*
Let's investigate this window
*/
int windowSum = 0;
/*
Add all items in the window
*/
for (int k = left; k <= right; k++) {
windowSum += nums[k];
}
/*
Did we beat the best sum seen so far?
*/
maximumSubArraySum = Math.max(maximumSubArraySum, windowSum);
}
}
return maximumSubArraySum;
}
}
/*
This code passes all Leetcode test cases as of Jan. 30 2019
Runtime: 129 ms, faster than 1.17% of Java online submissions for Maximum Subarray.
*/
class QuadraticTimeSolution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int maximumSubArraySum = Integer.MIN_VALUE;
for (int left = 0; left < n; left++) {
/*
Reset our running window sum once we choose a new
left bound to plant at. We then keep a new running
window sum.
*/
int runningWindowSum = 0;
/*
We improve be noticing we are performing duplicate
work. When we know the sum of the subarray from
0 to right - 1...why would we recompute the sum
for the subarray from 0 to right?
This is unnecessary. We just add on the item at
nums[right].
*/
for (int right = left; right < n; right++) {
/*
We factor in the item at the right bound
*/
runningWindowSum += nums[right];
/*
Does this window beat the best sum we have seen so far?
*/
maximumSubArraySum = Math.max(maximumSubArraySum, runningWindowSum);
}
}
return maximumSubArraySum;
}
}
/*
This code passes all Leetcode test cases as of Jan. 30 2019
Runtime: 6 ms, faster than 100.00% of Java online submissions for Maximum Subarray.
Kadane's algorithm - Dynamic Programming
Credit: Leetcode user @cbmbbz
*/
class LinearTimeSolution {
public int maxSubArray(int[] nums) {
/*
We default to say the the best maximum seen so far is the first
element.
We also default to say the the best max ending at the first element
is...the first element. (this is because on Leetcode we must choose a
subarray of at least one item, we cannot choose nothing)
*/
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
/*
We will investigate the rest of the items in the array from index
1 onward.
*/
for (int i = 1; i < nums.length; i++){
/*
We are inspecting the item at index i.
We want to answer the question:
"What is the Max Contiguous Subarray Sum we can achieve ending at index i?"
We have 2 choices:
maxEndingHere + nums[i] (extend the previous subarray best whatever it was)
1.) Let the item we are sitting at contribute to this best max we achieved
ending at index i - 1.
nums[i] (start and end at this index)
2.) Just take the item we are sitting at's value.
The max of these 2 choices will be the best answer to the Max Contiguous
Subarray Sum we can achieve for subarrays ending at index i.
Example:
index 0 1 2 3 4 5 6 7 8
Input: [ -2, 1, -3, 4, -1, 2, 1, -5, 4 ]
-2, 1, -2, 4, 3, 5, 6, 1, 5 'maxEndingHere' at each point
The best subarrays we would take if we took them:
ending at index 0: [ -2 ] (snippet from index 0 to index 0)
ending at index 1: [ 1 ] (snippet from index 1 to index 1) [we just took the item at index 1]
ending at index 2: [ 1, -3 ] (snippet from index 1 to index 2)
ending at index 3: [ 4 ] (snippet from index 3 to index 3) [we just took the item at index 3]
ending at index 4: [ 4, -1 ] (snippet from index 3 to index 4)
ending at index 5: [ 4, -1, 2 ] (snippet from index 3 to index 5)
ending at index 6: [ 4, -1, 2, 1 ] (snippet from index 3 to index 6)
ending at index 7: [ 4, -1, 2, 1, -5 ] (snippet from index 3 to index 7)
ending at index 8: [ 4, -1, 2, 1, -5, 4 ] (snippet from index 3 to index 8)
Notice how we are changing the end bound by 1 everytime.
*/
maxEndingHere = Math.max(maxEndingHere + nums[i], nums[i]);
/*
Did we beat the 'maxSoFar' with the 'maxEndingHere'?
*/
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}