Dynamic Programming
05. Maximum Subarray
Given an integer array nums, find the subarray with the largest sum and return its sum.
Examples
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum: 6.
Example 2
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum: 1.
Example 3
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum: 23.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Follow-up
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
from typing import List
nums: List[int] = [-2,1,-3,4,-1,2,1,-5,4]
max_sum: int = nums[0]
current_sum: int = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
print(max_sum)
# <fix>
# The old code reset current_sum to 0 when negative, so for all-negative arrays
# (e.g. [-3,-2,-5,-1]) it returned 0 instead of the largest negative (-1).
# Fixed using Kadane's algorithm: current_sum = max(nums[i], current_sum + nums[i])Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help