How do you approach Maximum Subarray?

Think about what happens at each position: should you start a new subarray or extend the current one?

What is the time complexity of Maximum Subarray?

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

What are common mistakes on Maximum Subarray?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

Sitelet https://gitgood.dev/coding/maximum-subarray

gitGood.dev

← Back to problems

Maximum Subarray

MediumAlgorithms

Description

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 an array.

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

Maximum Subarray: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

If you are stuck

Show the 3-step hint ladder

Think about what happens at each position: should you start a new subarray or extend the current one?
Kadane's algorithm maintains a running maximum ending at each position.
At each step, decide: current element alone vs current element + previous max.

The optimal approach

Show the approach: Kadane's Algorithm

At each position, calculate the maximum subarray ending at that position. It's either the element itself or the element plus the previous maximum.

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

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.