Kadane's Algorithm Explained — Maximum Subarray Sum in O(n)

package io.thecodeforge.algo;

import java.util.Arrays;

public class KadanePlainEnglish {

    public static long findMaxSubarraySum(int[] arr) {
        long currentSum = arr[0];
        long maxSum = arr[0];

        for (int i = 1; i < arr.length; i++) {
            // Core decision: extend or restart?
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            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("Array: " + Arrays.toString(arr));
        System.out.println("Max subarray sum: " + findMaxSubarraySum(arr)); // 6

        // Edge case: all negatives
        int[] allNeg = {-8, -3, -6, -2, -5};
        System.out.println("\nAll negatives: " + findMaxSubarraySum(allNeg)); // -2

        // Edge case: single element
        int[] single = {42};
        System.out.println("Single element: " + findMaxSubarraySum(single)); // 42
    }
}

package io.thecodeforge.algo;

public class KadaneBasic {

    /**
     * Finds the maximum sum of any contiguous subarray.
     * Uses Kadane's Algorithm — O(n) time, O(1) space.
     */
    public static long findMaxSubarraySum(int[] profits) {
        // Seed with first element — NEVER seed with 0
        long currentSum = profits[0];
        long maxSumFound = profits[0];

        for (int day = 1; day < profits.length; day++) {
            // Core decision: extend the current run, or start fresh today?
            currentSum = Math.max(profits[day], currentSum + profits[day]);
            maxSumFound = Math.max(maxSumFound, currentSum);
        }

        return maxSumFound;
    }

    public static void main(String[] args) {
        int[] dailyProfits = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Max subarray sum: " + findMaxSubarraySum(dailyProfits)); // 6

        int[] allLosses = {-8, -3, -6, -2, -5};
        System.out.println("All negatives: " + findMaxSubarraySum(allLosses)); // -2

        int[] oneDay = {42};
        System.out.println("Single element: " + findMaxSubarraySum(oneDay)); // 42
    }
}

package io.thecodeforge.algo;

public class KadaneWithIndices {

    static class SubarrayResult {
        final long maxSum;
        final int startIndex;
        final int endIndex;

        SubarrayResult(long maxSum, int startIndex, int endIndex) {
            this.maxSum = maxSum;
            this.startIndex = startIndex;
            this.endIndex = endIndex;
        }

        @Override
        public String toString() {
            return String.format("Max Sum: %d | Start: %d | End: %d", maxSum, startIndex, endIndex);
        }
    }

    /**
     * Kadane's extended to return subarray boundaries. O(n) time, O(1) space.
     */
    public static SubarrayResult findMaxSubarray(int[] values) {
        long currentSum = values[0];
        long maxSumFound = values[0];

        int potentialStart = 0;
        int bestStart = 0;
        int bestEnd = 0;

        for (int index = 1; index < values.length; index++) {
            // If starting fresh beats extending, reset and mark tentative start
            if (values[index] > currentSum + values[index]) {
                currentSum = values[index];
                potentialStart = index;
            } else {
                currentSum += values[index];
            }

            // Only commit boundaries when we confirm a new global maximum
            if (currentSum > maxSumFound) {
                maxSumFound = currentSum;
                bestStart = potentialStart;
                bestEnd = index;
            }
        }

        return new SubarrayResult(maxSumFound, bestStart, bestEnd);
    }

    public static void main(String[] args) {
        int[] stockReturns = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        SubarrayResult result = findMaxSubarray(stockReturns);
        System.out.println(result);

        // Print the actual subarray
        System.out.print("Subarray: [");
        for (int i = result.startIndex; i <= result.endIndex; i++) {
            System.out.print(stockReturns[i] + (i < result.endIndex ? ", " : "]\n"));
        }
    }
}

package io.thecodeforge.algo;

public class KadaneVsBruteForce {

    /** Brute Force: O(n^2) */
    public static long bruteForceMaxSum(int[] values) {
        long globalMax = values[0];
        for (int start = 0; start < values.length; start++) {
            long runningSum = 0;
            for (int end = start; end < values.length; end++) {
                runningSum += values[end];
                globalMax = Math.max(globalMax, runningSum);
            }
        }
        return globalMax;
    }

    /** Kadane's: O(n) */
    public static long kadaneMaxSum(int[] values) {
        long currentSum = values[0];
        long globalMax = values[0];
        for (int index = 1; index < values.length; index++) {
            currentSum = Math.max(values[index], currentSum + values[index]);
            globalMax = Math.max(globalMax, currentSum);
        }
        return globalMax;
    }

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

        long t1 = System.nanoTime();
        long brute = bruteForceMaxSum(data);
        long bruteTime = System.nanoTime() - t1;

        long t2 = System.nanoTime();
        long kadane = kadaneMaxSum(data);
        long kadaneTime = System.nanoTime() - t2;

        System.out.println("Brute: " + brute + " (" + bruteTime + " ns)");
        System.out.println("Kadane: " + kadane + " (" + kadaneTime + " ns)");
        System.out.println("Match: " + (brute == kadane));
    }
}