Maximum Subarray

medium
Arrays & HashingArrayDynamic ProgrammingDivide and Conquer

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous non-empty sequence of elements within the array.

Examples

Example 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.

Example 2

  • Input: nums = [1]
  • Output: 1
  • Explanation: The subarray [1] has the largest sum 1.

Example 3

  • Input: nums = [5,4,-1,7,8]
  • Output: 23
  • Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The simplest approach is to consider every possible subarray, compute its sum, and track the maximum. We use two nested loops to define the start and end of each subarray, and a running sum to efficiently compute each subarray's total. This guarantees we check all candidates but is slow for large inputs.

Algorithm

  1. Initialize maxSum to the smallest possible integer value.
  2. For each starting index i from 0 to n-1, initialize a running currentSum to 0.
  3. For each ending index j from i to n-1, add nums[j] to currentSum.
  4. Update maxSum if currentSum is greater than maxSum.
  5. Return maxSum after all subarrays have been checked.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxSum = INT_MIN;
        for (int i = 0; i < nums.size(); i++) {
            int currentSum = 0;
            for (int j = i; j < nums.size(); j++) {
                currentSum += nums[j];
                maxSum = max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
};
Java 21
class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                maxSum = Math.max(maxSum, currentSum);
            }
        }
        return maxSum;
    }
}
Python 3.12
def maxSubArray(nums: list[int]) -> int:
    max_sum = float('-inf')
    for i in range(len(nums)):
        current_sum = 0
        for j in range(i, len(nums)):
            current_sum += nums[j]
            max_sum = max(max_sum, current_sum)
    return max_sum
Go 1.26
func maxSubArray(nums []int) int {
    maxSum := nums[0]
    for i := 0; i < len(nums); i++ {
        currentSum := 0
        for j := i; j < len(nums); j++ {
            currentSum += nums[j]
            if currentSum > maxSum {
                maxSum = currentSum
            }
        }
    }
    return maxSum
}
Approach 2

Kadane's Algorithm

Intuition

Kadane's algorithm is based on a simple observation: at each position, the maximum subarray ending here is either the current element alone or the current element added to the maximum subarray ending at the previous position. If the running sum becomes negative, it is better to start a new subarray from the current element. We maintain a running sum and a global maximum, updating both as we scan through the array in a single pass.

Algorithm

  1. Initialize currentSum and maxSum both to the first element of the array.
  2. Iterate through the array starting from index 1.
  3. At each index, set currentSum to the maximum of nums[i] and currentSum + nums[i]. This decides whether to extend the previous subarray or start fresh.
  4. Update maxSum if currentSum exceeds it.
  5. Return maxSum.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            currentSum = max(nums[i], currentSum + nums[i]);
            maxSum = max(maxSum, currentSum);
        }
        return maxSum;
    }
};
Java 21
class Solution {
    public int maxSubArray(int[] nums) {
        int currentSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}
Python 3.12
def maxSubArray(nums: list[int]) -> int:
    current_sum = nums[0]
    max_sum = nums[0]
    for i in range(1, len(nums)):
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    return max_sum
Go 1.26
func maxSubArray(nums []int) int {
    currentSum := nums[0]
    maxSum := nums[0]
    for i := 1; i < len(nums); i++ {
        if currentSum+nums[i] > nums[i] {
            currentSum = currentSum + nums[i]
        } else {
            currentSum = nums[i]
        }
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    return maxSum
}
Approach 3

Divide and Conquer

Intuition

We can solve this using a divide and conquer strategy similar to merge sort. Split the array in half, recursively find the maximum subarray in the left half and the right half, and then find the maximum subarray that crosses the midpoint. The answer is the maximum of these three values. The crossing subarray is found by expanding left and right from the midpoint and summing greedily.

Algorithm

  1. Base case: if the subarray has one element, return that element.
  2. Find the midpoint and recursively compute the maximum subarray sum for the left half and right half.
  3. Compute the maximum crossing subarray by expanding left from mid and right from mid+1, tracking the best sum in each direction.
  4. Return the maximum of leftMax, rightMax, and crossMax.
TimeO(n log n)SpaceO(log n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    int helper(vector<int>& nums, int left, int right) {
        if (left == right) return nums[left];

        int mid = left + (right - left) / 2;
        int leftMax = helper(nums, left, mid);
        int rightMax = helper(nums, mid + 1, right);

        int leftSum = INT_MIN, rightSum = INT_MIN;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = max(leftSum, sum);
        }
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = max(rightSum, sum);
        }

        return max({leftMax, rightMax, leftSum + rightSum});
    }
};
Java 21
class Solution {
    public int maxSubArray(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {
        if (left == right) return nums[left];

        int mid = left + (right - left) / 2;
        int leftMax = helper(nums, left, mid);
        int rightMax = helper(nums, mid + 1, right);

        int leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftSum = Math.max(leftSum, sum);
        }
        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightSum = Math.max(rightSum, sum);
        }

        return Math.max(Math.max(leftMax, rightMax), leftSum + rightSum);
    }
}
Python 3.12
def maxSubArray(nums: list[int]) -> int:
    def helper(left: int, right: int) -> int:
        if left == right:
            return nums[left]

        mid = left + (right - left) // 2
        left_max = helper(left, mid)
        right_max = helper(mid + 1, right)

        left_sum = float('-inf')
        total = 0
        for i in range(mid, left - 1, -1):
            total += nums[i]
            left_sum = max(left_sum, total)

        right_sum = float('-inf')
        total = 0
        for i in range(mid + 1, right + 1):
            total += nums[i]
            right_sum = max(right_sum, total)

        return max(left_max, right_max, left_sum + right_sum)

    return helper(0, len(nums) - 1)
Go 1.26
func maxSubArray(nums []int) int {
    return helper(nums, 0, len(nums)-1)
}

func helper(nums []int, left, right int) int {
    if left == right {
        return nums[left]
    }

    mid := left + (right-left)/2
    leftMax := helper(nums, left, mid)
    rightMax := helper(nums, mid+1, right)

    leftSum := nums[mid]
    sum := 0
    for i := mid; i >= left; i-- {
        sum += nums[i]
        if sum > leftSum {
            leftSum = sum
        }
    }

    rightSum := nums[mid+1]
    sum = 0
    for i := mid + 1; i <= right; i++ {
        sum += nums[i]
        if sum > rightSum {
            rightSum = sum
        }
    }

    crossMax := leftSum + rightSum
    best := leftMax
    if rightMax > best {
        best = rightMax
    }
    if crossMax > best {
        best = crossMax
    }
    return best
}

Frequently asked questions

What is the optimal time complexity of Maximum Subarray?

The most efficient approach in this guide ("Divide and Conquer") runs in O(n log n) time and uses O(log n) extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Maximum Subarray use?

Maximum Subarray is a medium-level Arrays & Hashing problem involving Array, Dynamic Programming, Divide and Conquer. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Maximum Subarray be solved without extra space?

The most space-efficient approach in this guide uses O(log n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(log n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Maximum Product Subarray

Original problem: leetcode.com

Loading editor...
Input
nums=
[-2,1,-3,4,-1,2,1,-5,4]
Expected Output
6