Maximum Subarray
Medium
Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an array.
Examples:
Example 1:
Input:[-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output:6
Explanation:The subarray [4, -1, 2, 1] has the largest sum.
Example 2:
Input:[1]
Output:1
Example 3:
Input:[5, 4, -1, 7, 8]
Output:23
Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
Limits:
Time limit: 1000 ms
Memory limit: 128 MB
Topics
Dynamic Programming
Loading editor...
▶
Run your code to test against examples