Maximum Subarray
Medium · Dynamic Programming · Array · Divide and Conquer · Dynamic Programming
Problem
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum.
The subarray must be non-empty, so an all-negative array returns its largest (least negative) element.
Examples
Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6
[4,-1,2,1] sums to 6.
Input: nums = [-1] Output: -1
Non-empty, so you must take the single element.
Constraints
- 1 <= len(nums) <= 10^5
- -10^4 <= nums[i] <= 10^4
Approaches
- Brute force — every subarray — time O(n²), space O(1)
Follow-up
Once you have the linear solution, try a divide-and-conquer approach, which is more subtle.
Related problems
Start free on Cariara · Coding problems · System design studio
