Maximum Subarray Explained | Java | Dynamic Programming & Kadane’s Algorithm | Blind 75

Have you ever tried to find the most profitable contiguous period in a series of financial gains and losses?

When we see a problem like Maximum Subarray, our first instinct is usually:

“Let’s check every possible contiguous subarray and sum them up!”

When we write nested loops to check all contiguous subarrays:

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // sum elements from i to j
    }
}

we end up calculating overlapping sums repeatedly, leading to an inefficient O(N²) or O(N³) runtime.

This problem asks us to find a contiguous non-empty subarray with the maximum sum in linear time.

Companies like Google, Amazon, Meta, Microsoft, and Apple love this problem because it is the fundamental foundation of dynamic programming and contiguous array optimization.

In this article, we’ll build the intuition behind Maximum Subarray (LeetCode 53) from the Blind 75 list.

What You’ll Learn

By the end of this article you’ll know:

• ✅ Why checking all contiguous subarrays is inefficient
• ✅ The core decision rule: Extend vs. Reset
• ✅ Approach 1: Brute Force (O(N²) Time)
• ✅ Approach 2: Kadane’s Algorithm (O(N) Time, O(1) Space)
• ✅ Approach 3: Divide and Conquer (O(N log N) Time)
• ✅ Time and Space Complexity Analysis
• ✅ Interview Tips and Common Mistakes

Problem Statement

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 sum = 6.

Real-World Analogy

Imagine you are tracking daily net business profit over a multi-day period.

At any given day, you ask yourself:

“Should I add today’s profit/loss to my running multi-day total, or should I throw away the past total and start a brand new multi-day count today?”

If your running total from previous days has dropped below 0, keeping it only hurts your future sum. It is better to cut your losses, throw away the negative streak, and restart your count from today's number!

Important Concepts

The Core Local Decision

For any index i, we have two options for computing currentSum:

1. Option A (Extend): Add nums[i] to currentSum from previous elements.
2. Option B (Reset): Start a new subarray beginning at nums[i].

This gives us the famous Kadane’s Decision Formula:

currentSum = Math.max(nums[i], currentSum + nums[i])

If currentSum becomes negative before adding nums[i], then nums[i] is strictly greater than currentSum + nums[i]. Thus, negative prefixes are discarded automatically.

Approach 1: Brute Force (Building Intuition)

Before jumping to Kadane’s Algorithm, let’s examine the naive approach.

We can generate every possible contiguous range nums[i...j], accumulate the sum, and keep track of the maximum sum observed

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxSum = nums[0];

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}

Complexity

• Time Complexity: O(N²) — Two nested loops examining all N(N+1)/2 subarrays.
• Space Complexity: O(1) extra space.

Approach 2: Kadane’s Algorithm (Optimal O(N) Time, O(1) Space)

Kadane’s Algorithm solves the problem in a single pass using dynamic programming optimization.

Get Onlinecourses’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Key Variables

• currentSum: Maximum sum ending at index i.
• maxSum: Global maximum sum seen so far across all indices.

Java Code (Kadane’s Algorithm)

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            // Decide whether to add num to existing subarray or start new subarray
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            
            // Update global maximum
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }
}

Complexity Analysis

Kadane’s Algorithm

• Time Complexity: O(N) — Single pass over array of size N.
• Space Complexity: O(1) Auxiliary Space — Stores only scalar variables (currentSum, maxSum).

Approach 3: Divide and Conquer (O(N log N) Time)

Key Logic

Split the array at mid:

1. Maximum subarray lies entirely in the Left Half.
2. Maximum subarray lies entirely in the Right Half.
3. Maximum subarray crosses the Midpoint (starts in left half, ends in right half).

Java Code (Divide and Conquer)

class Solution {
    public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {
        if (left == right) {
            return nums[left];
        }

        int mid = left + (right - left) / 2;

        int leftMax = helper(nums, left, mid);
        int rightMax = helper(nums, mid + 1, right);
        int crossMax = maxCrossSum(nums, left, mid, right);

        return Math.max(leftMax, Math.max(rightMax, crossMax));
    }

    private int maxCrossSum(int[] nums, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }

        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        return leftSum + rightSum;
    }
}

Complexity Analysis

Divide and Conquer

• Time Complexity: O(N log N) — Recurrence T(N) = 2T(N/2) + O(N).
• Space Complexity: O(log N) Auxiliary Space — Recursion stack depth.

Interview Tips ⭐

Whenever an interviewer asks about maximum subarray sum:

1. Initialize correctly: Set currentSum and maxSum to nums[0], not 0. Setting them to 0 fails when all numbers in the array are negative (e.g., [-5, -2, -3]).
2. Transition smoothly: State how Kadane’s Algorithm (O(N)) is a space-optimized version of 1D Dynamic Programming.
3. Follow-up readiness: If asked to return the actual subarray elements rather than just the sum, maintain start, end, and tempStart pointer indices.

Common Mistakes

❌ Initializing maxSum = 0 Fails for negative arrays like nums = [-3, -1, -2]. Output should be -1, but initializing to 0 incorrectly returns 0.

❌ Resetting currentSum = 0 before checking nums[i] Checking Math.max(nums[i], currentSum + nums[i]) is cleaner and avoids edge-case mistakes compared to manual zero-reset checks.

💡 Key Takeaway

Kadane’s Algorithm is the foundational pattern for array optimization.

Remember this rule:

• Positive running sum ->Adds value to future elements (keep extending).
• Negative running sum ->Hurts future elements (discard and reset).

Conclusion

Maximum Subarray is a classic problem that demonstrates how dynamic programming converts an O(N²) brute-force algorithm into a clean O(N) linear pass.

We explored:

• Why negative prefix sums are discarded.
• Kadane’s Algorithm (O(N) Time, O(1) Space).
• The Divide and Conquer alternative (O(N log N) Time).

This article is part of my Blind 75 in Java series.

➡️ Next: Container With Most Water (LeetCode 11)

If you found this article helpful, consider following me for more beginner-friendly Java interview solutions.

Happy coding! 🚀