Kadane’s Algorithm

Understanding the Problem

The goal is to find the maximum sum of a contiguous subarray in a given array using Kadane's Algorithm.

Method 1: Kadane’s Algorithm

This method efficiently finds the maximum sum subarray in O(n) time.

public class KadaneAlgorithm {
    public static int kadaneAlgorithm(int[] arr) {
        int maxSum = Integer.MIN_VALUE, currentSum = 0;
        for (int num : arr) {
            currentSum += num;
            maxSum = Math.max(maxSum, currentSum);
            if (currentSum < 0)
                currentSum = 0;
        }
        return maxSum;
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum sum subarray: " + kadaneAlgorithm(arr));
    }
}
            

Output:

Maximum sum subarray: 6

Method 2: Brute Force Approach

This method checks all possible subarrays and calculates their sums, leading to an O(n²) complexity.

public class BruteForceMaxSubarray {
    public static int bruteForceMaxSubarray(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j < arr.length; j++) {
                sum += arr[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum sum subarray: " + bruteForceMaxSubarray(arr));
    }
}
            

Output:

Maximum sum subarray: 6

Method 3: Divide and Conquer Approach

This method uses recursion to divide the array and find the maximum sum subarray.

public class DivideAndConquerMaxSubarray {
    private static int max(int a, int b) { return Math.max(a, b); }
    
    private static int maxCrossingSum(int[] arr, int l, int m, int h) {
        int sum = 0, leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE;
        for (int i = m; i >= l; i--) {
            sum += arr[i];
            leftSum = Math.max(leftSum, sum);
        }
        sum = 0;
        for (int i = m + 1; i <= h; i++) {
            sum += arr[i];
            rightSum = Math.max(rightSum, sum);
        }
        return max(leftSum + rightSum, max(leftSum, rightSum));
    }
    
    private static int maxSubArraySum(int[] arr, int l, int h) {
        if (l == h) return arr[l];
        int m = (l + h) / 2;
        return max(maxSubArraySum(arr, l, m), max(maxSubArraySum(arr, m + 1, h), maxCrossingSum(arr, l, m, h)));
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum sum subarray: " + maxSubArraySum(arr, 0, arr.length - 1));
    }
}
            

Output:

Maximum sum subarray: 6