Description
Return the greatest sum of a nonempty contiguous subarray.
Solution
def max_sub_array(nums):
current = best = nums[0]
for i in range(1,len(nums)):
current = max(nums[i],current+nums[i])
best = max(best,current)
return bestExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[-4,2,3,-1]]- Output
5
The adjacent values 2 and 3 give five.
Example 2
- Input
[[-2,-5]]- Output
-2
The least negative single value wins.
Example 3
- Input
[[7]]- Output
7
The only subarray contains 7.
Approach
For each value, choose whether to extend the previous subarray or start a new one.
Time & space
O(n) time; O(1) space. Here n is the input length.