Algorithm Spotlight: Kadane’s Algorithm

Learn all about Kadane’s Algorithm in this fun and exciting guide!

Last Updated: October 10, 2020

Source

Problem: Maximum Subarray Problem

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest subarray sum = 6.
Input: nums = [-2147483647]
Output: -2147483647

Understanding the Problem

Approach 1: Brute Force

Approach 2: Kadane’s Algorithm (using Greedy method)

Approach 3: Kadane’s Algorithm (using Dynamic Programming)

Practice Problems

Thanks for reading! Don’t miss out on the next episode of Algorithm Spotlight!

Living in The Milky Way 😀