Maximum Subarray (Kadane's Algorithm)

Generated on 2025-07-10 02:02:35 Algorithm Cheatsheet for Technical Interviews

---

Maximum Subarray (Kadane’s Algorithm) - Cheatsheet

1. Quick Overview

Kadane’s Algorithm is a dynamic programming algorithm used to find the contiguous subarray within a one-dimensional array of numbers which has the largest sum. It’s efficient and easy to implement.

When to Use:

• Finding the largest sum of a contiguous subarray.
• When you need a linear-time solution (O(n)).
• When the array can contain positive, negative, and zero values.

2. Time & Space Complexity

Metric	Complexity	Explanation
Time Complexity	O(n)	The algorithm iterates through the array only once.
Space Complexity	O(1)	It uses a constant amount of extra space to store max_so_far and current_max. In-place algorithm.

3. Implementation

Here are implementations in Python, Java, and C++:

Python:

def max_subarray_kadane(nums):
    """
    Finds the maximum sum of a contiguous subarray using Kadane's Algorithm.

    Args:
        nums: A list of integers.

    Returns:
        The maximum subarray sum.
    """
    max_so_far = nums[0]  # Initialize the maximum sum found so far
    current_max = nums[0] # Initialize the current maximum sum

    for i in range(1, len(nums)):
        # Either extend the current subarray or start a new one from nums[i]
        current_max = max(nums[i], current_max + nums[i])

        # Update the global maximum if the current maximum is greater
        max_so_far = max(max_so_far, current_max)

    return max_so_far

# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray_kadane(nums)
print(f"Maximum subarray sum: {max_sum}")  # Output: 6

Java:

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int currentMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        return maxSoFar;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = sol.maxSubArray(nums);
        System.out.println("Maximum subarray sum: " + maxSum); // Output: 6
    }
}

C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxSubArray(vector<int>& nums) {
    int maxSoFar = nums[0];
    int currentMax = nums[0];

    for (int i = 1; i < nums.size(); i++) {
        currentMax = max(nums[i], currentMax + nums[i]);
        maxSoFar = max(maxSoFar, currentMax);
    }

    return maxSoFar;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int maxSum = maxSubArray(nums);
    cout << "Maximum subarray sum: " << maxSum << endl; // Output: 6
    return 0;
}

4. Common Patterns

• Finding the Start and End Indices: Modify the algorithm to track the start and end indices of the maximum subarray. Store the start index when a new current_max is initiated (i.e., current_max = nums[i]) and update the end index whenever max_so_far is updated.
• Circular Array: For a circular array, find the maximum subarray sum using Kadane’s algorithm. Then, invert the sign of all elements in the array and find the minimum subarray sum using Kadane’s algorithm. The maximum subarray sum in the circular array is either the maximum subarray sum found directly or the total sum of the array minus the minimum subarray sum.
• All Negative Numbers: If all numbers are negative, Kadane’s algorithm will return the largest negative number (least negative). You can add a check at the beginning to handle this case.
• Max Product Subarray: While Kadane’s algorithm directly applies to sum, the concept can be adapted for product by tracking both the maximum and minimum product ending at each position.

5. Pro Tips

• Initialization: Initialize max_so_far and current_max with the first element of the array, not 0. This handles cases where all numbers are negative.
• Empty Array: Handle the edge case of an empty array. Return 0 or throw an exception.
• Overflow: If dealing with very large numbers, consider using long or long long to prevent integer overflow.
• Debugging: Print the values of current_max and max_so_far in each iteration to understand how the algorithm works.
• Optimization: If the algorithm is used many times on the same array, consider pre-computing prefix sums for potential speedup in variations. However, for the basic Kadane’s algorithm, this is not necessary.

6. Practice Problems

• LeetCode 53. Maximum Subarray: This is the classic Kadane’s Algorithm problem.
• LeetCode 918. Maximum Sum Circular Subarray: A good problem to apply the circular array variation of Kadane’s Algorithm.
• LeetCode 152. Maximum Product Subarray: Adapts Kadane’s concept to find the maximum product.

7. Templates

These templates provide a basic structure that can be easily adapted to solve Maximum Subarray problems.

C++ Template

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int solve(vector<int>& nums) {
    // Handle edge case: empty array
    if (nums.empty()) {
        return 0; // Or throw an exception
    }

    int max_so_far = nums[0];
    int current_max = nums[0];

    for (int i = 1; i < nums.size(); ++i) {
        // Core Kadane's logic
        current_max = max(nums[i], current_max + nums[i]);
        max_so_far = max(max_so_far, current_max);
    }

    return max_so_far;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "Maximum subarray sum: " << solve(nums) << endl;
    return 0;
}

Python Template

def solve(nums):
    """
    Template for Maximum Subarray problem using Kadane's Algorithm.
    """
    if not nums:
        return 0  # Or raise an exception

    max_so_far = nums[0]
    current_max = nums[0]

    for i in range(1, len(nums)):
        # Core Kadane's logic
        current_max = max(nums[i], current_max + nums[i])
        max_so_far = max(max_so_far, current_max)

    return max_so_far


# Example usage
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = solve(nums)
print(f"Maximum subarray sum: {result}")

Java Template

class Solution {
    public int solve(int[] nums) {
        // Handle edge case: empty array
        if (nums == null || nums.length == 0) {
            return 0; // Or throw an exception
        }

        int maxSoFar = nums[0];
        int currentMax = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Core Kadane's Logic
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }

        return maxSoFar;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = sol.solve(nums);
        System.out.println("Maximum subarray sum: " + maxSum);
    }
}