Maximum Subarray

Problem

Given an integer array nums, return the sum of the contiguous subarray with the largest sum.

Constraints

• 1 ≤ nums.length ≤ 10⁵
• −10⁴ ≤ nums[i] ≤ 10⁴

Approach — Dynamic Programming

This is a Dynamic Programming problem. The idea: break the problem into overlapping subproblems and build the answer up, caching results so nothing is recomputed. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) to O(n²) time.

Solution code

Python

class Solution:
    def maxSubArray(self, nums):
        best = cur = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)
            best = max(best, cur)
        return best

Java

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;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.