Maximum Subarray Sum with One Deletion
Updated
Problem statement
You are given an integer array arr. Pick a non-empty subarray, then you may delete at most one element from it. Return the largest possible sum of what is left.
A subarray is a run of elements that are next to each other in arr. You can also delete nothing. After a delete, the subarray must still have at least one element, so you cannot pick a single element and then delete it.
Function
maximumSum(arr: int[]) â intExamples
Example 1
arr = [2,-3,1,4]return = 7Pick the whole array and delete -3. What is left is 2 + 1 + 4 = 7. Without a delete, the best is 1 + 4 = 5.
Example 2
arr = [-5,-1,-8]return = -1Every number is negative, so the best choice is the single element -1 with no delete. Deleting it is not allowed, because the subarray would become empty.
Example 3
arr = [3,-1,-1,4]return = 6Only one element can be deleted. Pick the whole array and delete one -1: 3 + (-1) + 4 = 6. Keeping both -1 values gives only 5.
Constraints
1 <= arr.length <= 10^5-10^4 <= arr[i] <= 10^4
More ServiceNow interview questions
Similar questions at other companies
- Maximum Product of a Contiguous SubarrayLinkedIn ¡ PHONE SCREENLinkedIn interview questions
- Fewest Coins CombinationBloomberg LP ¡ PHONE SCREENBloomberg LP interview questions
- Longest Increasing SubsequenceByteDance ¡ PHONE SCREENByteDance interview questions
- Jump GamePaytm ¡ PHONE SCREENPaytm interview questions
- Query Words Within K PositionsPalantir ¡ PHONE SCREENPalantir interview questions
- House RobberVisa ¡ PHONE SCREENVisa interview questions
- Best Improvement Period of at Least K IntervalsAmazon ¡ PHONE SCREEN
- Longest Increasing SubsequenceAngel One ¡ PHONE SCREEN
- Match Shops and BuyersGoogle ¡ PHONE SCREENGoogle interview questions
- Minimum Cost for a Target WeightPace Stock Broking Services ¡ PHONE SCREEN