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

/* | |

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; | |

} | |

} |