Maximum Subarray Sum with One Deletion
Mahabharata — The Exile's Dispensation — Remove One Cursed Day from the Pandava's Thirteen-Year Exile
एकं क्लेशं यदि त्यजेत् तदा लाभः महान्। कदम्बं कदम्बमेव — एकं विना श्रेष्ठम्॥
*If one pain is removed, the gain is great. The cluster is the cluster — without one, it is the best.*
The Story
The Pandavas had served twelve years of forest exile and one year of incognito — thirteen years total. But the celestial accountant Chitragupta posed a hypothetical: "If you could remove ONE day from your exile record — the single worst day — what would be the maximum cumulative net-positive stretch you could achieve?"
The battle-fortune array represented each day: positive for progress, negative for setback. You could delete at most ONE element entirely.
Mathematician Dhaumya formulated the problem: find the maximum subarray sum after removing at most one element.
"Two cases," Dhaumya said: 1. **No deletion**: Standard Kadane maximum subarray sum 2. **One deletion**: Remove one element from an otherwise good subarray
"For case 2, the optimal deletion is of the single most harmful element in the best subarray. Removing element at index i from the subarray splits it into two adjacent parts: everything to the left of i (best subarray ending at i-1) and everything to the right of i (best subarray starting at i+1)."
"So the score with deleting index i = `maxEndingHere[i-1] + maxStartingHere[i+1]`."
"We need two arrays: `maxEndingHere[i]` (best subarray sum ending exactly at i) and `maxStartingHere[i]` (best subarray sum starting exactly at i)."
But Dhaumya immediately improved on this: "We can compute this in ONE pass without storing full arrays."
Vidura showed the elegant O(1) space DP: - `maxNoDel`: max subarray sum ending at i with NO deletion used - `maxOneDel`: max subarray sum ending at i with EXACTLY ONE deletion used
Transitions: - `maxNoDel = max(arr[i], maxNoDel + arr[i])` — standard Kadane, no deletion - `maxOneDel = max(maxNoDel, maxOneDel + arr[i])` — either delete current element (use `maxNoDel` from previous position, skipping current) or extend the "one-deletion" subarray by adding current element
Wait — the second transition deserves careful reading: `maxOneDel` = max of: - `maxNoDel` (the best subarray ending at i-1, deleting the current element i) - `maxOneDel + arr[i]` (the best one-deletion subarray ending at i-1, extended by current element)
Vidura traced through `[1, -2, 0, 3]`: - i=0: noDel=1, oneDel=0 (no element to delete yet, treat as 0), res=1 - i=1: noDel=max(-2,1-2)=max(-2,-1)=-1. oneDel=max(1, 0-2)=max(1,-2)=1. res=max(1,1)=1 - i=2: noDel=max(0,-1+0)=max(0,-1)=0. oneDel=max(-1,1+0)=max(-1,1)=1. res=max(1,1)=1 - i=3: noDel=max(3,0+3)=3. oneDel=max(0,1+3)=4. res=max(1,4)=4 ✓
"Maximum with one deletion is 4," Vidura confirmed. "The subarray `[-2, 0, 3]` with `-2` deleted gives `0+3=3`... wait, or `[1, -2, 0, 3]` deleting `-2` gives `1+0+3=4`. Yes!"
The Pandavas metaphorically removed the darkest day from their exile record. The maximum net-positive stretch, with that single removal, became 4.
"One deletion, one pass, O(1) space," Dhaumya concluded. "Two DP states tracking parallel universes: one where no deletion has been used, one where exactly one deletion has been used."
This is Kadane's Algorithm extended for maximum subarray sum with one allowed deletion.
Dhaumya's First Instinct
Try all O(n) possible deletions. For each deletion, run standard Kadane on the remaining array. Track maximum. O(n²) time.
public int maximumSumBruteForce(int[] arr) {
int n = arr.length;
// Case 1: No deletion
int maxSum = kadane(arr);
// Case 2: Delete each element once
for (int del = 0; del < n; del++) {
int[] remaining = new int[n - 1];
int idx = 0;
for (int i = 0; i < n; i++) {
if (i != del) remaining[idx++] = arr[i];
}
maxSum = Math.max(maxSum, kadane(remaining));
}
return maxSum;
}
private int kadane(int[] arr) {
int maxS = arr[0], curr = arr[0];
for (int i = 1; i < arr.length; i++) {
curr = Math.max(arr[i], curr + arr[i]);
maxS = Math.max(maxS, curr);
}
return maxS;
}Vidura's Two-State Wisdom
public int maximumSum(int[] arr) {
int n = arr.length;
int maxNoDel = arr[0]; // Best ending at i, no deletion
int maxOneDel = 0; // Best ending at i, one deletion used (init 0: nothing deleted yet)
int result = arr[0];
for (int i = 1; i < n; i++) {
// One deletion: either delete arr[i] (use maxNoDel from prev)
// or extend the deletion subarray by arr[i]
maxOneDel = Math.max(maxNoDel, maxOneDel + arr[i]);
// No deletion: standard Kadane
maxNoDel = Math.max(arr[i], maxNoDel + arr[i]);
result = Math.max(result, Math.max(maxNoDel, maxOneDel));
}
return result;
}
// Test
public static void main(String[] args) {
System.out.println(new Solution().maximumSum(new int[]{1, -2, 0, 3})); // 4
System.out.println(new Solution().maximumSum(new int[]{1, -2, -2, 3})); // 3
System.out.println(new Solution().maximumSum(new int[]{-1, -1, -1, -1})); // -1
}Step-by-Step Walkthrough
arr = [-1, -1, -1, -1]
(all negative — best answer is a single element: -1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
i=0 (init): noDel=-1, oneDel=0, res=-1
i=1: oneDel=max(-1, 0-1)=max(-1,-1)=-1
noDel=max(-1,-1-1)=max(-1,-2)=-1
res=max(-1,-1,-1)=-1
i=2: oneDel=max(-1,-1-1)=max(-1,-2)=-1
noDel=max(-1,-1-1)=-1
res=-1
i=3: oneDel=max(-1,-1-1)=-1
noDel=max(-1,-1-1)=-1
res=-1
✅ Return -1 (even with one deletion, best is a single -1 element)
Note: result was initialized to arr[0]=-1, so even a length-1 subarray is considered.Deep Insight
**Why compute `maxOneDel` BEFORE `maxNoDel`?** `maxOneDel` uses `maxNoDel` from the PREVIOUS step. If we updated `maxNoDel` first, we'd be using the current step's value, which is wrong. The order matters.
**The `maxOneDel` transition decoded:** `maxOneDel = max(maxNoDel_prev, maxOneDel + arr[i])` - Option 1: `maxNoDel_prev` — the best subarray ending at i-1 without any deletion. By NOT including arr[i], we've effectively deleted it. This uses our one deletion on the current element. - Option 2: `maxOneDel + arr[i]` — we already used our deletion somewhere in the left portion; we're extending with arr[i] normally.
**Initialization subtlety:** `maxOneDel = 0` at start. This represents: "before the array begins, the best subarray with one deletion of nothing yet is 0." After the first element, `maxOneDel = max(arr[0] — skip this = 0, 0 + arr[0])`. The correct behavior emerges.
**What if all elements are negative?** The result is the maximum single element (Kadane's standard behavior). The one deletion doesn't help a single element.
**What if n=1?** We must keep the single element (deletion of only element gives empty array, but problem says non-empty). Result = arr[0].
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | n Kadane runs, each O(n) |
| Optimal | O(n) | O(1) | Two DP variables per step, single pass |
Pattern Recognition
✅ Maximum subarray with at most one element removed ✅ Two parallel DP states: with and without deletion ✅ Extension of Kadane for constrained deletion ✅ Order of state updates is critical **LeetCode Trigger Phrases:** → "maximum subarray" + "delete at most one element" → "one removal" + maximize subarray sum → "skip one element" + contiguous subarray
Bhagavad Gita 12.5
क्लेशोऽधिकतरस्तेषामव्यक्तासक्तचेतसाम्। अव्यक्ता हि गतिर्दुःखं देहवद्भिरवाप्यते॥
Greater is their difficulty whose minds are set on the unmanifest; for the goal of the unmanifest is very hard for embodied beings to attain.
Connection: The one deletion represents a single dispensation from difficulty — an embodied being's limited capacity to transcend one obstacle. The algorithm wisely tracks two states: the path without any grace (maxNoDel, the raw experience) and the path where one hardship has been lifted (maxOneDel). The maximum emerges from recognizing which dispensation yields the greatest liberation. Not infinite deletion — just one mindful release.