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:
7Explanation:
Skip -3 to get [1,4,-1,2,1] = 7.
Input:
nums = [5,-8,3,2,-4,6]Output:
13Explanation:
The maximum subarray sum allowing deletion of one element is 13, achieved by taking [5,-8,3,2,-4,6] and deleting -8 to get 5+3+2-4+6 = 12, or deleting -4 to get a higher sum. The optimal deletion yields 13.
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⁴