Algorithm Spotlight: Kadane’s Algorithm
Last Updated: October 10, 2020
Welcome back to the third episode of Algorithm Spotlight! In this episode, I’ll be talking about Kadane’s Algorithm!
Right before we begin, if you missed out on the previous episode, here’s Floyd’s Cycle Detection Algorithm:
Problem: Maximum Subarray Problem
Maximum Subarray - LeetCode
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum…
Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Explanation: [4,-1,2,1] has the largest subarray sum = 6.
Input: nums = [-2147483647]
Understanding the Problem
Right before we jump into solving this popular Maximum subarray problem, we need to understand the problem. We need to answer the 2 questions:
- What are we being asked to do and what are the limitations (eg. constraints, restrictions, etc.)?
- What is the input and output?
To start, we can tell that the problem says “find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.” Clearly, we can see that we are asked to find a non-empty array containing elements from the array that are adjacent to each other.
Our input for this problem is an array of integers and we are tasked to finding the output, an integer, which is the sum of the maximum subarray.
Now that we understand the problem, let’s solve it!
Approach 1: Brute Force
The easiest approach for this problem is through brute force. We can calculate all the possible subarrays, and calculate the sum of the values in each subarray, then update the maximum sum. We can implement this in O(n³) time:
Though this algorithm works, when there is a huge amount of data, we will get a TLE (Time Limit Exceeded). We need to make the algorithm more efficient. To start, we can note the following fact: We can calculate the sum simultaneously as we are looping through the array. This decreases our time complexity to O(n²) time. See the following pseudocode:
Finally! If we submit our solution to LeetCode’s Online Judge (OJ), we get an “Accepted” status, which means our solution passes all the pre-defined test cases. But this algorithm is still too slow, as we need to see each element in the array more than twice in the worst case. This is where algorithms come into play…
Approach 2: Kadane’s Algorithm (using Greedy method)
It turns out that this problem can be solved in O(n) time complexity using the Greedy method. The idea behind Kadane’s Algorithm is very simple. At each step, we loop through the array, and at each step, we see which sum is bigger: either the current element as a subarray or the previous subarray + the current element. We take this value and store it as the
local variable. Then we can update the globally maximum subarray value to
max(local, global). An example of the greedy method with
nums = [-6, 3, -9, 12, -14]:
The pseudocode below for this approach is shown here:
Approach 3: Kadane’s Algorithm (using Dynamic Programming)
Besides using the greedy method with Kadane’s Algorithm, we can also use Dynamic Programming (DP). The idea behind DP is to memorize the results so in future computations we save time. Click here for an excellent explanation on DP on Quora. The idea behind this is to have a
global variable, which is the sum of the maximum subarray, and the
local variable, the sum of the current subarray (which may not be optimal). Then, we iterate through the entire array and add the number
local , then update
global if necessary. If
local is ever 0, we reset
local back to 0.
As practice makes perfect, here are some Kadane’s Algorithms problems where you will apply your newly-aquired skills to some fun problems!
Best Time to Buy and Sell Stock - LeetCode
Say you have an array for which the i th element is the price of a given stock on day i. If you were only permitted to…
- Draw out a few cases on paper. Note the pattern that we need to find max(prices[j]-prices[i]).
- This problem is exactly the same as Maximum Subarray, except for a few minor modifications.
Best Time to Buy and Sell Stock II - LeetCode
Say you have an array prices for which the i th element is the price of a given stock on day i. Design an algorithm to…
- Make sure you understand the problem on the top before solving this one.
- Use math or a modified greedy approach from the first Best Time to Buy and Sell Stock problem.