Interview challenge · medium · array, dynamic-programming, kadane
Maximum Subarray
El reto
El enunciado va en inglés, igual que en el vídeo.
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).
La solución
# 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