mediumArraysDynamic Programming 0 views
Maximum Subarray
Find the contiguous subarray with the largest sum.
Given an integer array nums, find the subarray with the largest sum, and return that sum.
A subarray is a contiguous non-empty sequence of elements within an array.
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 = [5,4,-1,7,8]
Output: 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.
Hints
Companies
No companies reported yet.
Discussion
Sign in to join the discussion.
Loading discussion...
Test results
No test cases yet.