Skip to content

1186. Maximum Subarray Sum with One Deletion 👍

Approach 1: 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  // Similar to 53. Maximum Subarray
  int maximumSum(vector<int>& arr) {
    // dp[0][i] := the maximum sum subarray ending in i (no deletion)
    // dp[1][i] := the maximum sum subarray ending in i (at most 1 deletion)
    vector<vector<int>> dp(2, vector<int>(arr.size()));

    dp[0][0] = arr[0];
    dp[1][0] = arr[0];
    for (int i = 1; i < arr.size(); ++i) {
      dp[0][i] = max(arr[i], dp[0][i - 1] + arr[i]);
      dp[1][i] =
          max({arr[i], dp[1][i - 1] + arr[i], dp[0][i - 1] /*delete arr[i]*/});
    }

    return ranges::max(dp[1]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  // Similar to 53. Maximum Subarray
  public int maximumSum(int[] arr) {
    // dp[0][i] := the maximum sum subarray ending in i (no deletion)
    // dp[1][i] := the maximum sum subarray ending in i (at most 1 deletion)
    int[][] dp = new int[2][arr.length];

    dp[0][0] = arr[0];
    dp[1][0] = arr[0];
    for (int i = 1; i < arr.length; ++i) {
      dp[0][i] = Math.max(arr[i], dp[0][i - 1] + arr[i]);
      dp[1][i] = Math.max(arr[i], Math.max(dp[1][i - 1] + arr[i], dp[0][i - 1] /*delete arr[i]*/));
    }

    return Arrays.stream(dp[1]).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  # Very similar to 53. Maximum Subarray
  def maximumSum(self, arr: List[int]) -> int:
    # dp[0][i] := the maximum sum subarray ending in i (no deletion)
    # dp[1][i] := the maximum sum subarray ending in i (at most 1 deletion)
    dp = [[0] * len(arr) for _ in range(2)]

    dp[0][0] = arr[0]
    dp[1][0] = arr[0]
    for i in range(1, len(arr)):
      dp[0][i] = max(arr[i], dp[0][i - 1] + arr[i])
      dp[1][i] = max(arr[i], dp[1][i - 1] + arr[i], dp[0][i - 1])

    return max(dp[1])

Approach 2: $O(1)$ DP

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
 public:
  // Similar to 53. Maximum Subarray
  int maximumSum(vector<int>& arr) {
    constexpr int kMin = INT_MIN / 2;
    int ans = kMin;
    int zero = kMin;  // no deletion
    int one = kMin;   // <= 1 deletion

    for (const int a : arr) {
      one = max({a, one + a, zero /*delete a*/});
      zero = max(a, zero + a);
      ans = max(ans, one);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
  // Similar to 53. Maximum Subarray
  public int maximumSum(int[] arr) {
    final int kMin = Integer.MIN_VALUE / 2;
    int ans = kMin;
    int zero = kMin; // no deletion
    int one = kMin;  // <= 1 deletion

    for (final int a : arr) {
      one = Math.max(a, Math.max(one + a, zero /*delete a*/));
      zero = Math.max(a, zero + a);
      ans = Math.max(ans, one);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  # Very similar to 53. Maximum Subarray
  def maximumSum(self, arr: List[int]) -> int:
    ans = -math.inf
    zero = -math.inf  # no deletion
    one = -math.inf   # <= 1 deletion

    for a in arr:
      one = max(a, one + a, zero)
      zero = max(a, zero + a)
      ans = max(ans, one)

    return ans