Max Subarray Sum by Removing At Most One

Time: O(n)

Space: O(1)

Problem Overview

Classic Kadane tracks the best subarray sum ending at each index.

Intuition

Classic Kadane tracks the best subarray sum ending at each index. Allow deleting at most one element anywhere in that subarray: maintain a second running value for “best sum ending here after exactly one removal.”

Algorithm

1curr_sum = Kadane without removal (max ending at i). skipped_sum = max ending at i with one element removed in the subarray.
2At index i: skipped_sum = max(curr_sum, skipped_sum + arr[i]) — skip arr[i] using prior Kadane tail, or extend a subarray that already used its one skip.
3curr_sum = max(curr_sum + arr[i], arr[i]); max_sum = max(max_sum, curr_sum, skipped_sum).
4Initialize all three to arr[0] for single-element arrays and all-negative cases.

Example Walkthrough

Input: arr = [1, -2, 0, 3]

1. i=1: skipped_sum=max(1,-2)=1, curr_sum=max(-1,-2)=-1, max_sum=1.
2. i=2: skipped_sum=max(-1,1)=1, curr_sum=0, max_sum=1.
3. i=3: skipped_sum=max(0,4)=4, curr_sum=3, max_sum=4 (drop -2, take 0 and 3).

Output: 4

Common Pitfalls

• Do not reset skipped_sum to 0 — “remove one element” means omit it from the subarray, not zero it out.
• Removing zero elements is allowed; answer is ordinary Kadane when no skip helps.
• O(n) time, O(1) space; same DP as LC 1186 (Maximum Subarray Sum with One Deletion).

Max Subarray Sum by Removing At Most One.java

Java

// Approach: Kadane with one optional skip — curr_sum is best ending at i with no removal;
// skipped_sum is best ending at i after removing exactly one element.
// Time: O(n) Space: O(1)
class Solution {

    public int maxSumSubarray(int[] arr) {
        int curr_sum = arr[0];
        int max_sum = arr[0];
        int skipped_sum = 0;
        for (int i = 1; i < arr.length; i++) {
            skipped_sum = Math.max(curr_sum, skipped_sum + arr[i]);
            curr_sum = Math.max(curr_sum + arr[i], arr[i]);
            max_sum = Math.max(max_sum, Math.max(curr_sum, skipped_sum));
        }
        return max_sum;
    }
}

Was this solution helpful?