Medium
Maximum Subarray
- Time limit
- 2 s
- Memory limit
- 256 MB
- Estimated
- 20 min
- Dynamic Programming
Description
Description
Given an integer array nums, find the contiguous subarray (containing at least one element) that has the largest sum, and return its sum.
A subarray must consist of consecutive elements. The subarray must be non-empty. The array may contain negative numbers only, in which case the answer is the least-negative element.
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
Example 3
- Input:
nums = [-3, -1, -2] - Output:
-1 - Explanation: Every subarray sum is negative; the largest is the single element
-1.
Expected Function Behavior
Constraints
1 <= nums.length <= 100000-10000 <= nums[i] <= 10000- The subarray must contain at least one element.
- The answer fits in a signed 32-bit integer.
Sample cases
3Sample 1
Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Expected output
6
Sample 2
Input
nums = [1]
Expected output
1
Skills and languages
Patterns
- Linear DP
- Kadane's Algorithm
Languages
- Python 3
Solve this problem
Create a free account to write, run and submit your solution.
- Write Python or Java in the browser, with your draft saved as you type
- Run your code on the examples as often as you like
- Submit to a sandboxed judge and see exactly which case failed
- Ask the AI mentor for a hint without being handed the answer