thesarfo

Reference

Maximum Subarray Sum (Kadane's Algorithm)

Finding the contiguous subarray with the largest sum, from O(n³) brute force down to Kadane's O(n) single pass, plus a variant that returns the subarray itself.

views 0

Contiguous subarray with the largest sum. (LeetCode 53)

Brute force: every subarray’s sum computed directly — O(n³), or O(n²) by tracking a running sum as the end index expands instead of recomputing from scratch.

Optimal — Kadane’s Algorithm (O(n)): track a running currentSum and the best seen maxSoFar. Add each element to currentSum; if it exceeds maxSoFar, update maxSoFar; if currentSum ever goes negative, reset it to 0 (a negative running sum can only hurt any future subarray, so it’s better to start fresh).

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int currentSum = 0;


        for (int num : nums) {
            currentSum += num;
            maxSoFar = Math.max(maxSoFar, currentSum);


            if (currentSum < 0) {
                currentSum = 0;
            }
        }


        return maxSoFar;
    }
}

Time: O(n). Space: O(1).

Variant — return the subarray itself, not just its sum: track the start/end indices whenever a new best sum is found.

public static long[] maxSubarraySumWithIndices(int[] arr, int n) {
    long maxSum = arr[0];
    int currentSum = 0;
    int start = 0, ansStart = 0, ansEnd = 0;


    for (int i = 0; i < n; i++) {
        if (currentSum == 0) {
            start = i; // mark potential start of a new subarray
        }


        currentSum += arr[i];


        if (currentSum > maxSum) {
            maxSum = currentSum;
            ansStart = start;
            ansEnd = i;
        }


        if (currentSum < 0) {
            currentSum = 0;
        }
    }


    long[] subarray = new long[ansEnd - ansStart + 1];
    for (int i = ansStart; i <= ansEnd; i++) {
        subarray[i - ansStart] = arr[i];
    }


    return subarray;
}