Description
Given an integer array nums, find the contiguous subarray with the largest sum and return its sum. You may also skip exactly one element.
Examples
Input:
nums = [-2,1,-3,4,-1,2,1,-5,4]Output:
10Explanation:
Skip -3 to get [1,4,-1,2,1] = 7.
Input:
nums = [5,-8,3,2,-4,6]Output:
12Explanation:
Deleting -8 gives the best sum, which is 12, so the answer is 12.
Input:
nums = [-1,-2,-3]Output:
-1Explanation:
All elements are negative. Without skipping: maximum subarray is [-1] = -1. With skipping one element: one could take subarray [-1,-3] (skip -2) = -4, or [-2,-3] (skip -1) = -5, or [-1,-2] (skip -3) = -3. All options with skipping are worse than just taking [-1] = -1.
Constraints
- •
1 ≤ nums.length ≤ 10⁵ - •
-10⁴ ≤ nums[i] ≤ 10⁴