Maximum Subarray with Jump
MediumArray
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⁴