40. Best Stretch Sum
A hiking app records the change in altitude at every checkpoint of a trail: positive numbers are climbs and negative numbers are descents. A hiker wants to find the continuous stretch of checkpoints, containing at least one checkpoint, that gains the most altitude in total.
Write a method maxSubarraySum that takes the array nums of altitude changes and returns the largest possible sum of a non-empty contiguous section of nums. If every value is negative, the best stretch is the single checkpoint with the smallest loss.
Example 1
- Input:
- nums = [-2,1,-3,4,-1,2,1,-5,4]
- Output:
- 6
- Explanation:
The stretch 4, -1, 2, 1 gains 6 in total, which is the best possible.
Example 2
- Input:
- nums = [5,4,-1,7,8]
- Output:
- 23
- Explanation:
Taking the whole trail gives 5 + 4 - 1 + 7 + 8 = 23.
Constraints
1 ≤ nums.length ≤ 1000
-104 ≤ nums[i] ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)