Problem statement

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

Solution

We use here the idea of Leetcode 0053. Maximum Subarray. But now we keep for each i the sum of biggest subarray ends with index i and also sum of biggest subarray starts with index i. Then for each index i we look at sum dp1[i-1] + dp2[i+1]. Also do not forgot about the case when we delete nothing.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def maximumSum(self, A):
        def cadane(A):
            dp = [0] * len(A)
            dp[0] = A[0]
            for i in range(1, n):
                dp[i] = max(A[i], A[i] + dp[i-1])
            return dp
        
        n, ans = len(A), -float("inf")
        dp1, dp2 = cadane(A), cadane(A[::-1])[::-1]
        for i in range(1, n-1):
            ans = max(ans, dp1[i-1] + dp2[i+1])
        return max(ans, max(dp1))