Find Largest Sum Contiguous Subarray

Understanding the Problem

The goal is to find the subarray with the maximum sum in a given array using different methods.

Method 1: Kadane's Algorithm

This method efficiently finds the largest sum contiguous subarray using dynamic programming.

public class MaxSubarrayKadane {
    public static int maxSubArraySum(int[] arr) {
        int maxSoFar = arr[0], maxEndingHere = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum contiguous sum: " + maxSubArraySum(arr));
    }
}
            

Output:

Maximum contiguous sum: 6

Method 2: Divide and Conquer

This method finds the largest sum subarray by dividing the array into halves recursively.

public class MaxSubarrayDivideConquer {
    public 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 Math.max(Math.max(leftSum + rightSum, leftSum), rightSum);
    }
    public static int maxSubArraySum(int[] arr, int l, int h) {
        if (l == h) return arr[l];
        int m = (l + h) / 2;
        return Math.max(Math.max(maxSubArraySum(arr, l, m), 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 contiguous sum: " + maxSubArraySum(arr, 0, arr.length - 1));
    }
}
            

Output:

Maximum contiguous sum: 7

Method 3: Brute Force

This method checks all subarrays and computes their sums to find the maximum sum.

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

Output:

Maximum contiguous sum: 6