Java Concepts and DSA

Kadane's Algorithm

Anurag Srivastava's photo
Anurag Srivastava
·

3 min read

Kadane's Algorithm: Finding the Maximum Contiguous Subarray Sum in Java

The problem of finding the maximum sum of a contiguous subarray within a given array of integers is a classic challenge in computer science. This post explores two approaches to solving this problem in Java: a brute-force method and the highly efficient Kadane's Algorithm. We'll compare their time complexities and demonstrate their implementations.

The Problem:

Given an array of integers (which can include positive, negative, and zero values), find the contiguous subarray with the largest sum and return that sum.

1. Brute-Force Approach (O(n^2) Time Complexity)

The brute-force approach involves checking the sum of all possible subarrays. We use nested loops: the outer loop selects the starting index, and the inner loop calculates the sum of all subarrays starting from that index.

Java

public class MaxSubarraySum {

    public static int maxSubarraySumBruteForce(int[] arr) {
        int maxSum = Integer.MIN_VALUE; // Initialize with the smallest possible integer

        for (int i = 0; i < arr.length; i++) { // Outer loop: starting index
            for (int j = i; j < arr.length; j++) { // Inner loop: ending index
                int currentSum = 0;
                for (int k = i; k <= j; k++) { // Calculate sum of subarray from i to j
                    currentSum += arr[k];
                }
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
    // ... (Kadane's Algorithm will go here)

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSumBruteForce = maxSubarraySumBruteForce(arr);
        System.out.println("Maximum Subarray Sum (Brute Force): " + maxSumBruteForce);


        int maxSumKadane = maxSubarraySumKadane(arr);
        System.out.println("Maximum Subarray Sum (Kadane's Algorithm): " + maxSumKadane);

    }
}

  • Time Complexity: O(n^2) due to the nested loops.

  • Space Complexity: O(1) as we use only constant extra space.

  • Disadvantage: Inefficient for larger arrays.

2. Kadane's Algorithm (O(n) Time Complexity)

Kadane's algorithm provides a much more efficient solution with linear time complexity. The core idea is to keep track of two values:

  • max_so_far: Stores the maximum sum found so far.

  • current_max: Stores the maximum sum ending at the current position.

Java

public static int maxSubarraySumKadane(int[] arr) {
    int maxSoFar = Integer.MIN_VALUE;
    int currentMax = 0;

    for (int num : arr) {
        currentMax += num;

        if (currentMax < 0) {
            currentMax = 0;  // Reset if the current sum becomes negative
        }

        maxSoFar = Math.max(maxSoFar, currentMax); // Update max_so_far
    }
    return maxSoFar;
}

  • Time Complexity: O(n) as we iterate through the array only once.

  • Space Complexity: O(1) as we use only constant extra space.

  • Advantage: Highly efficient, even for large datasets.

Explanation of Kadane's Algorithm:

The algorithm's key insight is that a negative subarray sum will never contribute to a larger overall sum. If current_max becomes negative, we reset it to 0, effectively starting a new subarray from the next element. We continually update max_so_far to keep track of the largest sum encountered.

Which Approach to Use?

Kadane's Algorithm is the clear winner due to its superior time complexity. For any array of significant size, the brute-force approach will be considerably slower. Kadane's algorithm is the standard and most efficient way to solve the maximum contiguous subarray sum problem.

kadane's algorithm