1186. Maximum Subarray Sum with One Deletion

https://leetcode.com/problems/maximum-subarray-sum-with-one-deletion/

53. Maximum Subarray is the prerequisite to understand this solution.

Let

S0(n) be the set of all subarrays ending at index n, without deletion. Same as S(n) in Problem 53.
S1(n) be the set of all subarrays ending at index n (before deletion), with at most one deletion.
- S0(0) is a subset of S1(n)
P0(n) be the max sum of all subarrays in S0(n). It can be obtained in the same approach as in Problem 53.
P1(n) be the max sum of all subarrays in S1(n).

Here, we want to establish a recurrence relation from P1(n) to P0(n-1), P0(n) and P1(n-1).

We can classify subarrays in S1(n) into 3 categories:

The index of deleted item is n. All subarrays in this case belong to S0(n-1), since there must be no deletion in the subarray arr[i..n-1].
The index of deleted item is before n. Any subarray in this case can be obtained by combining some subarray in S1(n-1) and arr[n].
No deletion. Same as S0(n).

Given above, we have the recurrence relation as below:

P1(n) = max(P0(n-1), P1(n-1) + arr[n], P0(n))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        P0 = arr[:]
        P1 = arr[:]
        for n in range(1, len(arr)):
            P0[n] = max(P0[n-1] + arr[n], arr[n])
            P1[n] = max(P0[n-1], P1[n-1] + arr[n], P0[n])
        return max(P1)

Optimization is left to the reader.