75. Maximum Subarray · DSA Practice

Find the contiguous subarray (at least one element) with the largest sum and return that sum.

Example 1

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

Output: 6

Explanation: [4, −1, 2, 1] has the largest sum, 6.

Example 2

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

Output: -1

Explanation: All values are negative: pick the largest single value.

Hint 1

If the running sum becomes worse than starting fresh at the current element, restart.

Dynamic ProgrammingKadane

Approach 1: All subarrays

Two loops with a running sum.

⏱ Time O(n²)💾 Space O(1)

Approach 2: Kadane’s algorithm

Best subarray ending here = max(x, previous + x).

⏱ Time O(n)💾 Space O(1)

Approach 3: Divide and conquer ✅

Combine left, right and crossing answers.

⏱ Time O(n log n)💾 Space O(log n)

Reference solution for Divide and conquer (time O(n log n), space O(log n)). Each solution passes every test in all four languages.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        best = cur = nums[0]
        for x in nums[1:]:
            cur = max(x, cur + x)     # extend the run, or restart at x
            best = max(best, cur)
        return best

class Solution {
    public int maxSubArray(int[] nums) {
        int best = nums[0], cur = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);   // extend or restart (Kadane)
            best = Math.max(best, cur);
        }
        return best;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int best = nums[0], cur = nums[0];
        for (size_t i = 1; i < nums.size(); i++) {
            cur = max(nums[i], cur + nums[i]);        // extend or restart (Kadane)
            best = max(best, cur);
        }
        return best;
    }
};

function maxSubArray(nums) {
  let best = nums[0], cur = nums[0];
  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]); // extend or restart (Kadane)
    best = Math.max(best, cur);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (1-D).