FastPrepMaximum Subarray Sum with One Deletion

Maximum Subarray Sum with One Deletion

ServiceNow logoServiceNow● MediumFULLTIMEPHONE SCREEN

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[]) → int

Examples

Example 1

arr = [2,-3,1,4]return = 7

Pick 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 = -1

Every 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 = 6

Only 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

All ServiceNow interview questionsSee ServiceNow hiring insights
Saved
class Solution {
    public int maximumSum(int[] arr) {
        // Write your code here.
    }
}
Checking account…