Maximum Subarray

Find the contiguous subarray with the largest sum, and return that sum.

MediumMust DoKadane's AlgorithmLeetCode

Why solve this?

Kadane's algorithm is one of the most frequently reused running-aggregate patterns in interviews.

Pattern recognition

"Maximum/minimum sum of a contiguous subarray" is Kadane's algorithm: at each position decide whether to extend the running subarray or restart from here.

Prerequisites

Arrays

Hints

A subarray is contiguous — this rules out sorting or reordering.
At each index, either extend the previous subarray or start a new one from here — which is worth more?
Keep a running best-so-far as you scan.

Approach

Maintain `currentSum`, the best sum of a subarray ending exactly at the current index. At each element, `currentSum = max(nums[i], currentSum + nums[i])` — either the running subarray is still worth extending, or the current element alone is a better restart. Track the maximum `currentSum` seen across the whole scan as `bestSum`.

Java solution

Solution.java

class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int bestSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            bestSum = Math.max(bestSum, currentSum);
        }
        return bestSum;
    }
}

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