Maximum Subarray Sum with One Deletion

• This problem extends maximum subarray sum by allowing at most one element deletion from the chosen subarray.
• Two DP states at each position: noDel (no deletion) and oneDel (one deletion used).
• noDel = max(nums[i], noDel + nums[i]) follows standard Kadane.
• oneDel = max(oneDel + nums[i], prevNoDel) captures two transitions.
• Snapshot prevNoDel before overwriting to avoid a dependency bug.
• Time is O(N) and space is O(1).

What is the Maximum Subarray Sum with One Deletion problem?

Given an array of integers, find the maximum sum of a contiguous non-empty subarray where you may delete at most one element from the subarray. This is LeetCode 1186.

For example, given [1, -2, 0, 3], the maximum sum without deletion is 3 (just [3]), but with one deletion we can remove -2 from [1, -2, 0, 3] to get [1, 0, 3] with sum 4.

How do the two states work?

At each index, we maintain two values.

• noDel: the maximum sum of a subarray ending here with no deletion.
• oneDel: the maximum sum of a subarray ending here with exactly one deletion used somewhere inside it.

package com.bank.service;

public class MaxSubarrayOneDeleteService {

    /**
     * Finds the best P&L run allowing one outlier day to be struck out.
     * Used by the National Bank of India risk management team.
     */
    public static long maxSumWithOneDeletion(long[] pnl) {
        long noDel = pnl[0];
        long oneDel = 0; // No deletion possible with a single element
        long globalMax = pnl[0];

        for (int i = 1; i < pnl.length; i++) {
            // Snapshot noDel before overwriting
            long prevNoDel = noDel;

            // Standard Kadane for noDel
            noDel = Math.max(pnl[i], noDel + pnl[i]);

            // oneDel: extend existing deletion, or delete current element
            oneDel = Math.max(oneDel + pnl[i], prevNoDel);

            // Track best across both states
            globalMax = Math.max(globalMax, Math.max(noDel, oneDel));
        }
        return globalMax;
    }

    public static void main(String[] args) {
        long[] pnl = {10000, -50000, 20000, 30000, -5000};
        System.out.println("Best run (with one strike-out): Rs."
            + maxSumWithOneDeletion(pnl));
        System.out.println("Best run (no strike-out): Rs."
            + maxSubarraySum(pnl));
    }

    private static long maxSubarraySum(long[] arr) {
        long cur = arr[0], best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur = Math.max(arr[i], cur + arr[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

javac -d out com/bank/service/MaxSubarrayOneDeleteService.java
java -cp out com.bank.service.MaxSubarrayOneDeleteService

Best run (with one strike-out): Rs.60000
Best run (no strike-out): Rs.45000

Why does oneDel = max(oneDel + nums[i], prevNoDel) work?

The one-deletion state can be reached in two ways.

1. Extend a run that already used its deletion by adding the current element: oneDel + nums[i].
2. Delete the current element from the best no-deletion run ending at the previous index: this is simply prevNoDel, because removing the current element leaves exactly that previous run.

The second transition is the clever part: it encodes deleting the current element without ever trying deletions explicitly, which keeps the whole algorithm linear.

Why is the snapshot ordering critical?

We must compute the new oneDel using the previous noDel value, not the just-updated one. If we overwrite noDel first and then use it for oneDel, we would be deleting an element from a run that already includes the current element, which is wrong.

// WRONG: uses already-updated noDel
noDel = Math.max(pnl[i], noDel + pnl[i]);
oneDel = Math.max(oneDel + pnl[i], noDel); // Bug! noDel already updated

// CORRECT: snapshot first
long prevNoDel = noDel;
noDel = Math.max(pnl[i], noDel + pnl[i]);
oneDel = Math.max(oneDel + pnl[i], prevNoDel); // Uses previous value

What are the edge cases?

Several edge cases require attention.

• Two elements: can delete one, so the answer is the max of each element alone or both together.
• All negative: the answer is the largest element (no deletion helps, or deleting the worst of two elements).
• Single element: cannot delete from a single-element subarray (it would be empty), so the answer is that element.
• Deletion not needed: if the best subarray has no bad elements, the no-deletion state wins.

package com.bank.core;

public class OneDeleteEdgeCases {
    public static void main(String[] args) {
        System.out.println(maxWithDel(new long[]{10000, -5000}));  // 10000
        System.out.println(maxWithDel(new long[]{-3, -5, -1}));    // -1
        System.out.println(maxWithDel(new long[]{42}));             // 42
    }

    static long maxWithDel(long[] arr) {
        long noDel = arr[0], oneDel = 0, best = arr[0];
        for (int i = 1; i < arr.length; i++) {
            long prev = noDel;
            noDel = Math.max(arr[i], noDel + arr[i]);
            oneDel = Math.max(oneDel + arr[i], prev);
            best = Math.max(best, Math.max(noDel, oneDel));
        }
        return best;
    }
}

10000
-1
42

What is the time and space complexity?

Time is O(N): a single pass with constant work per element. Space is O(1): three scalar variables plus a snapshot. This is optimal.

How does this generalize to K deletions?

The pattern extends naturally to at-most-k deletions by carrying k+1 states: state[0] through state[k], where state[j] is the best sum ending here with exactly j deletions used. Each state j can extend from state[j] or delete from state[j-1]. Time becomes O(N * K) and space O(K).

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Kadane lifted into two states: this is the canonical example of adding a dimension to Kadane's state space.
• The snapshot-ordering pitfall: computing oneDel after updating noDel is the most common bug.
• Forward-backward approach: an alternative is to compute max subarray sums ending at each index (forward) and starting at each index (backward), then find the index whose exclusion gives the best combined sum. This is O(N) time and O(N) space.
• Non-empty constraint: after deletion, the subarray must still be non-empty, which means you cannot delete from a single-element subarray.