Understanding Maximum Subarray (Kadane's Algorithm) in Java

Introduction & Problem Explanation

The Maximum Subarray problem asks us to find a contiguous subarray within a one-dimensional array of numbers (which contains at least one positive number) that has the largest sum.

For example, in the array [-2, 1, -3, 4, -1, 2, 1, -5, 4], the contiguous subarray with the largest sum is [4, -1, 2, 1], which sums up to 6. Finding this efficiently is critical because contiguous sequence maximization is a common subproblem in data analysis and signal processing.

The Algorithmic Approach

1. The Naive Approach (O(n²))

We can check every possible starting and ending index for all subarrays, sum their elements, and record the maximum. This requires two nested loops, yielding a time complexity of O(n²). For large datasets, this approach is extremely slow and impractical.

2. Kadane's Algorithm (O(n) Time, O(1) Space)

Kadane's algorithm is a classic dynamic programming technique that solves the problem in a single pass. At each index, we make a local greedy decision: Is it better to add the current element to our existing running sum, or should we discard the current sum and start a brand-new subarray starting exactly at the current element? By taking Math.max(nums[i], currSum + nums[i]), we dynamically build the optimal subarray sum in O(n) time using only O(1) extra space.

Step-by-Step Execution Walkthrough

Let's trace Kadane's algorithm on the input array nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

1. Step 1 (Initialization): We initialize two variables: currSum (current running subarray sum) and maxSum (global maximum subarray sum seen so far). We set both to the first element of the array:
   • currSum = -2
   • maxSum = -2
2. Step 2 (Index i = 1, Value = 1):
   • We compare the current element 1 against the sum of the element and the previous running sum: Math.max(1, currSum + 1) = Math.max(1, -2 + 1) = 1.
   • So, currSum = 1 (we discard the negative history and start a new subarray here).
   • Update global maximum: maxSum = Math.max(maxSum, currSum) = Math.max(-2, 1) = 1.
3. Step 3 (Index i = 2, Value = -3):
   • Calculate new running sum: Math.max(-3, currSum + (-3)) = Math.max(-3, 1 - 3) = -2.
   • So, currSum = -2 (we continue the subarray because -2 is better than starting fresh with -3).
   • Update global maximum: maxSum = Math.max(1, -2) = 1.
4. Step 4 (Index i = 3, Value = 4):
   • Calculate new running sum: Math.max(4, currSum + 4) = Math.max(4, -2 + 4) = 4.
   • So, currSum = 4 (we start a new subarray since 4 is greater than the accumulated 2).
   • Update global maximum: maxSum = Math.max(1, 4) = 4.
5. Step 5 (Index i = 4, Value = -1):
   • Calculate new running sum: Math.max(-1, 4 - 1) = 3. So, currSum = 3.
   • Update global maximum: maxSum = Math.max(4, 3) = 4.
6. Step 6 (Index i = 5, Value = 2):
   • Calculate new running sum: Math.max(2, 3 + 2) = 5. So, currSum = 5.
   • Update global maximum: maxSum = Math.max(4, 5) = 5.
7. Step 7 (Index i = 6, Value = 1):
   • Calculate new running sum: Math.max(1, 5 + 1) = 6. So, currSum = 6.
   • Update global maximum: maxSum = Math.max(5, 6) = 6.
8. Step 8 (Index i = 7, Value = -5):
   • Calculate new running sum: Math.max(-5, 6 - 5) = 1. So, currSum = 1.
   • Update global maximum: maxSum = Math.max(6, 1) = 6.
9. Step 9 (Index i = 8, Value = 4):
   • Calculate new running sum: Math.max(4, 1 + 4) = 5. So, currSum = 5.
   • Update global maximum: maxSum = Math.max(6, 5) = 6.
10. Step 10 (Completion): The iteration completes, and the maximum subarray sum recorded is 6 (corresponding to the segment [4, -1, 2, 1]).

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• currSum = Math.max(nums[i], currSum + nums[i]): This is the core dynamic programming state transition. It decides whether the current element should extend the previous subarray or start a new one.
• maxSum = Math.max(maxSum, currSum): This ensures we capture the peak value of currSum at any point during the single-pass traversal.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.Arrays;

public class MaximumSubarray {

    // Brute Force - O(n^2)
    public int maxSubArrayBrute(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    // Optimized - O(n) (Kadane's Algorithm)
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0], currSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        MaximumSubarray solver = new MaximumSubarray();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};

        System.out.println("--- Maximum Subarray (Kadane's) Demonstration ---");
        System.out.println("Input Array: " + Arrays.toString(nums));

        System.out.println("\nExecuting Kadane's Algorithm...");
        int maxSum = nums[0], currSum = nums[0];
        System.out.printf("Initial state: currSum = %d, maxSum = %d\n", currSum, maxSum);
        
        for (int i = 1; i < nums.length; i++) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
            System.out.printf("After element %d (val=%d): currSum = %d, maxSum = %d\n", 
                i, nums[i], currSum, maxSum);
        }
        System.out.println("Maximum contiguous subarray sum: " + solver.maxSubArray(nums));
    }
}

Conclusion

Solving the Maximum Subarray (Kadane's Algorithm) problem highlights how we can leverage key data structures and algorithmic paradigms (like two pointers, hash maps, or dynamic programming) to significantly optimize runtime and simplify code complexity.