Maximum Subarray Sum with One Deletion
Description
You get an integer array arr.
Pick a non-empty contiguous subarray, and optionally delete one value from it, so that the values left have the largest possible sum. The subarray must still have at least one value after the deletion.
Return that largest sum.
Examples
Example 1
Input: arr = [1, -2, 0, 3]
Output: 4
Explanation: Delete -2 from the whole array: 1 + 0 + 3 = 4.
Example 2
Input: arr = [1, -2, -2, 3]
Output: 3
Explanation: Only one value can go, so the two -2s can't both be skipped. The best is [3], 3.
Example 3
Input: arr = [-1, -1, -1, -1]
Output: -1
Explanation: Deleting the only value of a one-value subarray would leave nothing, which isn't allowed. The best is a single -1.
Constraints
- 1 ≤ arr.length ≤ 10^5
- -10^4 ≤ arr[i] ≤ 10^4
Editorial
Brute Force
Intuition
Try every subarray. If you delete one value from it, the best one to delete is its smallest, so each subarray gives two candidates: its sum, and (with two or more values) its sum minus its smallest value. Keep the running sum and the running smallest as the end moves right.
Step-by-Step Explanation
For arr = [1, -2, 0, 3]:
- Try every subarray. Each one counts as it is, and, when it has two or more values, with its smallest value deleted. The best starts at the largest single value, 3.
- arr[0..0] adds up to 1.
- arr[0..1] adds up to −1, or 1 without its smallest value, −2.
- arr[0..2] adds up to −1, or 1 without its smallest value, −2.
- arr[0..3] adds up to 2, or 4 without its smallest value, −2. That's a new best.
- arr[1..1] adds up to −2.
- arr[1..2] adds up to −2, or 0 without its smallest value, −2.
- arr[1..3] adds up to 1, or 3 without its smallest value, −2.
- arr[2..2] adds up to 0.
- arr[2..3] adds up to 3, or 3 without its smallest value, 0.
- arr[3..3] adds up to 3.
- The answer is 4, after trying all 10 subarrays.
Every Subarray, With and Without Its Smallest Value — The shaded cells are the subarray being tried.
Algorithm
best= the largest single value.- For each start s, extend the end e to the right, keeping
totalandlow(the smallest value so far). - Each subarray:
best = max(best, total), and if it has two or more values,best = max(best, total − low).
Code
class Solution {
public:
int maximumSum(vector<int>& arr) {
int n = arr.size(), best = *max_element(arr.begin(), arr.end());
for (int s = 0; s < n; s++) {
int total = 0, low = arr[s];
for (int e = s; e < n; e++) { // every subarray that starts at s
total += arr[e];
low = min(low, arr[e]);
best = max(best, total);
if (e > s) best = max(best, total - low); // delete its smallest value, keeping at least one
}
}
return best;
}
};
class Solution:
def maximumSum(self, arr: list[int]) -> int:
n, best = len(arr), max(arr)
for s in range(n):
total, low = 0, arr[s]
for e in range(s, n): # every subarray that starts at s
total += arr[e]
if arr[e] < low:
low = arr[e]
if total > best:
best = total
if e > s and total - low > best: # delete its smallest value, keeping at least one
best = total - low
return best
class Solution {
public int maximumSum(int[] arr) {
int n = arr.length, best = Integer.MIN_VALUE;
for (int v : arr) best = Math.max(best, v);
for (int s = 0; s < n; s++) {
int total = 0, low = arr[s];
for (int e = s; e < n; e++) { // every subarray that starts at s
total += arr[e];
low = Math.min(low, arr[e]);
best = Math.max(best, total);
if (e > s) best = Math.max(best, total - low); // delete its smallest value, keeping at least one
}
}
return best;
}
}
var maximumSum = function(arr) {
const n = arr.length;
let best = Math.max(...arr);
for (let s = 0; s < n; s++) {
let total = 0, low = arr[s];
for (let e = s; e < n; e++) { // every subarray that starts at s
total += arr[e];
low = Math.min(low, arr[e]);
best = Math.max(best, total);
if (e > s) best = Math.max(best, total - low); // delete its smallest value, keeping at least one
}
}
return best;
};
Complexity Analysis
Time Complexity: O(n²)
n(n + 1)/2 subarrays, each updated in O(1).
Space Complexity: O(1)
Why This Approach Is Not Efficient
10^5 values have about 5 · 10^9 subarrays (over the time limit in cpp and Python and java and javascript).
Kadane's already finds the best subarray with nothing deleted in one pass. The only extra thing the next step needs to know is whether a deletion has been used up, so carry one more number for that case.
Optimal Approach - Kadane's with Two States
Intuition
Carry two bests for subarrays that end at the current value:
none: nothing deleted. That's Kadane's:none = max(x, none + x).one: exactly one value deleted. Either the deletion happened earlier and x is kept,one + x, or x itself is deleted, which leaves the best that ended just before it with nothing deleted, the oldnone. Soone = max(one + x, old none).
Compute one before changing none. At the first value nothing can be deleted (the subarray would be empty), so one starts far below any real sum. The answer is the largest none or one seen.
Step-by-Step Explanation
For arr = [1, -2, 0, 3]:
- At the first value, none (nothing deleted) is 1. Nothing can be deleted yet, since that would leave an empty subarray.
- For one, the best is to delete −2 itself, keeping 1, so one is 1. Kadane's makes none −1.
- For one, the best is to keep 0 after the earlier deletion, 1 + 0 = 1, so one is 1. Kadane's makes none 0.
- For one, the best is to keep 3 after the earlier deletion, 1 + 3 = 4, so one is 4. Kadane's makes none 3. That's a new best.
- The answer is 4, from one pass.
With and Without a Deletion — The highlighted value is the one being added; the panel shows none, one and best after it.
Algorithm
none = arr[0],one = −∞,best = arr[0].- For each next value x:
one = max(one + x, none), thennone = max(x, none + x), thenbest = max(best, none, one). - Return
best.
In Java and C++ use half of the smallest int instead of −∞, so one + x can't overflow.
Code
class Solution {
public:
int maximumSum(vector<int>& arr) {
const int NOT_YET = INT_MIN / 2; // far below any real sum, and safe to add to
int none = arr[0], one = NOT_YET, best = arr[0];
for (size_t i = 1; i < arr.size(); i++) {
int x = arr[i];
one = max(one + x, none); // keep x after an earlier deletion, or delete x itself
none = max(x, none + x); // plain Kadane's, after one has read the old value
best = max({best, none, one});
}
return best;
}
};
class Solution:
def maximumSum(self, arr: list[int]) -> int:
none = arr[0] # best sum ending here, nothing deleted
one = float('-inf') # best sum ending here, one value deleted: not possible yet
best = arr[0]
for x in arr[1:]:
one = max(one + x, none) # keep x after an earlier deletion, or delete x itself
none = max(x, none + x) # plain Kadane's, after one has read the old value
best = max(best, none, one)
return best
class Solution {
public int maximumSum(int[] arr) {
final int NOT_YET = Integer.MIN_VALUE / 2; // far below any real sum, and safe to add to
int none = arr[0], one = NOT_YET, best = arr[0];
for (int i = 1; i < arr.length; i++) {
int x = arr[i];
one = Math.max(one + x, none); // keep x after an earlier deletion, or delete x itself
none = Math.max(x, none + x); // plain Kadane's, after one has read the old value
best = Math.max(best, Math.max(none, one));
}
return best;
}
}
var maximumSum = function(arr) {
let none = arr[0]; // best sum ending here, nothing deleted
let one = -Infinity; // best sum ending here, one value deleted: not possible yet
let best = arr[0];
for (let i = 1; i < arr.length; i++) {
const x = arr[i];
one = Math.max(one + x, none); // keep x after an earlier deletion, or delete x itself
none = Math.max(x, none + x); // plain Kadane's, after one has read the old value
best = Math.max(best, none, one);
}
return best;
};
Complexity Analysis
Time Complexity: O(n)
One pass.
Space Complexity: O(1)
Three numbers, whatever the length.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Starting the deletion state at 0. none = one = 0
On arr = [-1, -1, -1, -1], it returns 0; the answer is -1. Before the first value, "one value deleted" would mean deleting the only value and keeping nothing. Starting it at 0 lets that empty subarray count, so an all-negative array returns 0. Start it far below any real sum.
Updating none before one. none = max(x, none + x) # then one
On arr = [1, -2, 0, 3], it returns 3; the answer is 4. Deleting x leaves the best sum that ended just BEFORE x. If none has already taken x in, "delete x" quietly keeps it: on [1, -2, 0, 3] the deletion of -2 never happens.
Deleting the smallest value of the array. i = arr.index(min(arr))
On arr = [-10, 5, -1, 5], it returns 9; the answer is 10. The best value to delete belongs to the best subarray, and needn't be the smallest one overall. On [-10, 5, -1, 5] deleting -1 gives 10; deleting -10 leaves [5, -1, 5], whose best is 9.
Where This Pattern Is Taught
This problem practises Kadane's with an extra state for a used-up choice. It's taught in Kadane's Algorithm with More State.