Loading problem…
Given an integer array nums, find the contiguous subarray (containing at least one element) which has the largest sum, and return its sum. A subarray is a contiguous part of the array. For example, in [-2,1,-3,4,-1,2,1,-5,4], the subarray [4,-1,2,1] has the largest sum of 6.
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] sums to 6. Extending it in either direction adds a negative total, so 6 is the largest.
Example 2
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: Every prefix of the array has a positive total, so taking the whole array gives the largest sum: 5 + 4 - 1 + 7 + 8 = 23.
Example 3
Input: nums = [1]
Output: 1
Explanation: The only subarray is [1], with sum 1.
At index `i`, ask: *is the best subarray ending here the one I was already extending, or should I start fresh?* If my running sum has gone negative, it can only hurt future extensions — reset it.
Run checks all cases above. Submit evaluates all test cases.