Maximum Subarray Sum with One Deletion LeetCode solution in Python

1
class Solution:
2
    def maximumSum(self, arr: List[int]) -> int:
3
        n = len(arr)
4
        if n == 1:
5
            return arr[0]
6
        dpLeft = [-(10**4) - 1 for _ in range(n)]
7
        dpLeft[0] = arr[0]
8
        i = 1
9
        while i < n:
10
            dpLeft[i] = max(arr[i], dpLeft[i - 1] + arr[i])
11
            i += 1
12
        dpRight = [-(10**4) - 1 for _ in range(n)]
13
        dpRight[-1] = arr[-1]
14
        j = n - 2
15
        while j >= 0:
16
            dpRight[j] = max(arr[j], dpRight[j + 1] + arr[j])
17
            j -= 1
18
        k = 0
19
        maxi = -(10**4) - 1
20
        while k < n:
21
            # if we take it
22
            curr_maxi_with = dpRight[k] + dpLeft[k] - arr[k]
23

24
            if k == 0:
25
                curr_maxi_without = dpRight[k + 1]
26
            elif k == n - 1:
27
                curr_maxi_without = dpLeft[k - 1]
28
            else:
29
                if dpLeft[k - 1] >= 0 and dpRight[k + 1] >= 0:
30
                    curr_maxi_without = dpRight[k + 1] + dpLeft[k - 1]
31
                else:
32
                    curr_maxi_without = max(dpLeft[k - 1], dpRight[k + 1])
33

34
            maxi = max(maxi, curr_maxi_without, curr_maxi_with)
35
            k += 1
36

37
        return maxi