Arrays & Hashing · 004Medium
Maximum Subarray
Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Examples
maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) -> 6 // [4,-1,2,1] maxSubArray([1]) -> 1 // single element maxSubArray([-3, -1, -2]) -> -1 // all negative maxSubArray([5, 4, -1, 7, 8]) -> 23 // the whole array maxSubArray([0, -3, 0]) -> 0 // best sum is 0, from a single 0 maxSubArray([2, -1, 2, -1, 2]) -> 4 // a dip is worth crossing
Edge cases
- All numbers negative — the answer is the single largest element, not 0.
- Single element.
- FOLLOW-UP
- If you have figured out the O(n) solution, try coding another solution using the divide and
- conquer approach.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — sum every subarray.
- Target
- O(n) time, O(1) space — Kadane's algorithm: at each index keep the best sum ending here.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/004-maximum-subarray.js ./practice c 004