Interview challenge · medium · array, dynamic-programming, kadane
Maximum Subarray
The challenge
Given an integer array nums, find the contiguous subarray (with at least one number) that has the largest sum, and return that sum.
Example
[-2, 1, -3, 4, -1, 2, 1, -5, 4] -> 6 ([4, -1, 2, 1])
[1] -> 1
[5, 4, -1, 7, 8] -> 23Idea: Kadane's algorithm. The best subarray ending here either extends the best one ending at the previous element or starts fresh at this element. Track that running value and the best seen. Time O(n), space O(1).
The solution
# Maximum Subarray - ayotl.dev
def max_subarray(nums):
# Kadane: best sum ending right here
cur = best = nums[0]
for n in nums[1:]:
# extend the run, or start over
cur = max(n, cur + n)
best = max(best, cur)
return best
print(max_subarray(
[-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([1]))
print(max_subarray([5, 4, -1, 7, 8]))
$ python3 maximum_subarray.py
6
1
23