Back to problems
Leetcode
Medium
Arrays
Dynamic Programming
Divide and Conquer
Google
Maximum Subarray
Find the contiguous subarray with the largest possible sum.
Acceptance 40%
Problem Statement
Problem
Given an integer array, choose a contiguous subarray with the maximum possible sum and return that sum.
A subarray must contain at least one element.
Notes
- The subarray has to be contiguous.
- If all values are negative, the answer is the largest single element.
Input Format
- An integer array
nums. nums[i]may be positive, negative, or zero.
Output Format
- Return a single integer: the maximum subarray sum.
Constraints
- The subarray must be non-empty.
- Consider all contiguous subarrays.
- A linear-time solution is expected for interview use.
Examples
Sample cases returned by the problem API.
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, which is 6.
Example 2
Input
nums = [1]
Output
1
Explanation
The only subarray is [1].
Show 1 more example
Example 3
Input
nums = [-8,-3,-6,-2,-5,-4]
Output
-2
Explanation
All numbers are negative, so the best choice is the largest single element.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.
Guided hints
Editorial and discussion links
Concept map and variants
Track your progress
Sign in to bookmark this problem, save notes, and manage its revision plan.