Kadane’s Algorithm

Introduction

Ever wondered how to find the best continuous segment in a sequence of numbers? Whether it’s maximizing profits in a stock market or identifying the happiest streak in your life, Kadane’s Algorithm is your go-to solution for finding the maximum sum of a contiguous subarray. 🚀

This guide breaks down Kadane’s Algorithm, its real-world analogy, step-by-step implementation, and advanced variations to level up your problem-solving skills. Let’s dive in!

What is Kadane’s Algorithm?

Kadane’s Algorithm is a dynamic programming gem that efficiently finds the maximum sum of a contiguous subarray within a one-dimensional array of numbers (positive or negative). With a time complexity of O(n) and space complexity of O(1), it’s both fast and memory-efficient.

Real-Life Analogy

Imagine your life as a sequence of days—some are awesome (positive numbers), and some are tough (negative numbers). Kadane’s Algorithm helps you find the best continuous period in your life that maximizes your happiness. It’s like asking, “Should I keep going with this streak, or start fresh today?” 😄

How Kadane’s Algorithm Works

The algorithm is elegantly simple. It iterates through the array, keeping track of two variables:

max_current: The maximum sum of the subarray ending at the current index.
max_global: The maximum sum found so far across all subarrays.

Algorithm Steps

Initialize max_current and max_global to the first element of the array.
Loop through the array starting from the second element:
- Update max_current as the maximum of the current element alone or the sum of max_current and the current element.
- Update max_global if max_current is greater.
Return max_global as the result.

Here’s the Python implementation:

def kadane(arr):
    max_current = max_global = arr[0]
    
    for i in range(1, len(arr)):
        max_current = max(arr[i], max_current + arr[i])
        max_global = max(max_global, max_current)
    
    return max_global
 
# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(kadane(arr))  # Output: 6 (subarray: [4, -1, 2, 1])

Time & Space Complexity

Time Complexity: O(n) — single pass through the array.
Space Complexity: O(1) — only two variables are used, regardless of array size.

Why Kadane’s Algorithm Matters

Kadane’s Algorithm is a cornerstone for solving array-based problems in competitive programming and real-world applications. It’s efficient, intuitive, and adaptable to variations like circular arrays or maximum product subarrays. Plus, it’s a favorite in coding interviews! 🔥

5 Master Problems to Master Kadane’s Algorithm

Here are five problems (including the classic and its variations) to solidify your understanding and impress interviewers:

1️⃣ Maximum Subarray Sum (Kadane’s Classic)

Platform: LeetCode 53
Problem: Find the contiguous subarray with the largest sum (at least one number).
Example:
- Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
- Output: 6 (subarray: [4, -1, 2, 1])
Skill Built: Core Kadane’s Algorithm.

2️⃣ Maximum Sum Circular Subarray

Platform: LeetCode 918
Problem: Find the maximum sum subarray in a circular array (last element connects to the first).
Example:
- Input: [5, -3, 5]
- Output: 10 (subarray: [5, 5] via circular wrap)
Skill Built: Modify Kadane to handle circular arrays by computing:
- Normal max subarray (using Kadane).
- Total array sum minus the minimum subarray (modified Kadane).

3️⃣ Maximum Product Subarray

Platform: LeetCode 152
Problem: Find the maximum product of a contiguous subarray.
Example:
- Input: [2, 3, -2, 4]
- Output: 6 (subarray: [2, 3])
Skill Built: Adapt Kadane to track both maximum and minimum products at each step (since negative × negative = positive).

4️⃣ Maximum Subarray Sum with One Deletion

Platform: LeetCode 1186
Problem: Find the maximum sum subarray, allowing at most one element deletion.
Skill Built: Extend Kadane with dynamic programming to track sums with and without deletion.

5️⃣ Longest Subarray with Sum ≤ K

Platform: InterviewBit, Codeforces, etc.
Problem: Find the longest contiguous subarray with a sum less than or equal to K.
Skill Built: Combine Kadane with sliding window and prefix sum techniques.

Pro Tip from Kadane Baba 😄

"Zindagi ke har mod pe decide karo — akele chalna sahi hai ya purane rishte nibhane chahiye. Jo bhi zyada fayda de, wahi best hai."
Translation: At every step, decide whether to start fresh or continue with the past. Choose what gives you the maximum gain!

Conclusion 🎯

By now, you should have a solid grasp of Kadane’s Algorithm: ✅ What it is and how it works ✅ Its real-world analogy and implementation ✅ How to tackle advanced variations ✅ Why it’s a must-know for coding interviews

Kadane’s Algorithm is a powerful tool for solving array-based problems efficiently. Practice the five master problems above, and you’ll be ready to crush any subarray challenge! 🚀

Stay tuned for more deep dives into algorithms and problem-solving techniques! 🔥