Largest Sum of Any Contiguous Subarray

Medium15–20 min

Topics

ArrayDynamic Programming

Companies

AmazonMicrosoftGoogleLinkedIn

Given an array nums that may contain negative numbers, return the largest possible sum of any non-empty contiguous subarray. Trying every subarray works, but re-summing overlapping ranges from scratch throws away most of the previous work. Kadane's Algorithm answers this in one pass: keep a running sum, and whenever it dips below zero, abandon it and start over at the next element — a negative running total can never help a future subarray, so restarting is always at least as good as carrying it forward.

Test Case 1:

Input:nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Output:6

Explanation:The subarray [4, -1, 2, 1] has the largest sum: 6.

Test Case 2:

Input:nums = [1]

Output:1

Explanation:A single element is its own largest (and only) subarray.

Test Case 3:

Input:nums = [5, 4, -1, 7, 8]

Output:23

Explanation:Every element is worth keeping, so the best subarray is the whole array.

Constraints

◆1 ≤ nums.length ≤ 10⁵
◆-10⁴ ≤ nums[i] ≤ 10⁴

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 4-10 integers, -15 to 15

1	class Solution {
2	public int maxSubarraySum(int[] nums) {
3	int maxSum = nums[0];
4	int currentSum = nums[0];
5	for (int i = 1; i < nums.length; i++) {
6	currentSum = Math.max(nums[i], currentSum + nums[i]);
7	maxSum = Math.max(maxSum, currentSum);
8	}
9	return maxSum;
10	}
11	}
12

-2

-3

-1

-5

↑i

Variables

maxSum-2

currentSum-2

INITIALIZE

Start both maxSum and currentSum at nums[0] = -2.

Step 1 / 18

Approach & Solutions

Brute Force

Brute

For every possible starting index, extend the subarray one element at a time, tracking the running sum and comparing it against the best seen so far. Correct, but every extension re-derives a sum that a single pass could track incrementally instead.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int maxSubarraySum(int[] nums) {
        int maxSum = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
}

Optimal — Kadane's Algorithm

Optimal

This is Kadane's Algorithm — the technique this whole group of problems is named after. Walk the array once, keeping a running currentSum. At each element, decide: is it better to extend the subarray that ends at the previous element, or to abandon it and start fresh here? A negative currentSum can only drag down whatever it's added to, so once it goes negative, restarting is always at least as good. Track the best currentSum seen as the answer.

TimeO(n)