Maximum Subarray Sum with One Deletion

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maximumSum(self, a: List[int]) -> int:
        n = len(a)
        maxEndHere = [0] * n
        maxStartHere = [0] * n
        max_sum = a[0]
        maxEndHere[0] = a[0]

        for i in range(1, n):
            maxEndHere[i] = max(a[i], maxEndHere[i - 1] + a[i])
            max_sum = max(max_sum, maxEndHere[i])

        maxStartHere[n - 1] = a[n - 1]
        for i in range(n - 2, -1, -1):
            maxStartHere[i] = max(a[i], maxStartHere[i + 1] + a[i])

        for i in range(1, n - 1):
            max_sum = max(max_sum, maxEndHere[i - 1] + maxStartHere[i + 1])

        return max_sum