Algorithm Spotlight: Kadane’s Algorithm
Learn all about Kadane’s Algorithm in this fun and exciting guide!
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
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest subarray sum = 6.Example 2:
Input: nums = [-2147483647]
Output: -2147483647Understanding 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 tomax(local, global). An example of the greedy method withnums = [-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 i into local , then update global if necessary. If local is ever 0, we reset local back to 0.
Practice Problems
As practice makes perfect, here are some Kadane’s Algorithms problems where you will apply your newly-aquired skills to some fun problems!
Hints:
- 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.
Hints:
- 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.
