Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.
Note that the subarray needs to be non-empty after deleting one element.
 
Example 1:
Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.
Example 2:
Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:
Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

 
Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

Difficulty: interview

Starter code:

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        

Solutions:
import sys
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        ignore=0
        not_ignore=0
        res=-sys.maxsize
        for i in arr:
            if i>=0:
                ignore+=i
                not_ignore+=i
            else:
                if ignore==0:
                    ignore+=i
                else:
                    ignore=max(ignore+i,not_ignore)
                not_ignore+=i
            res=max(res,ignore)
            if ignore<0:
                ignore=0
            if not_ignore<0:
                not_ignore=0
        return res


class Solution(object):
    def maximumSum(self, arr):
        dp, res = [arr[0], 0], arr[0]
        for i in range(1, len(arr)):
            dp[1] = max(dp[0], dp[1]+arr[i])
            dp[0] = max(arr[i], arr[i]+dp[0])
            res = max(res, dp[0], dp[1])
        return res

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            if i >= 2:
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
                
        return max(max_ending_here1)

class Solution:
    def maximumSum(self, arr: List[int]) -> int:        
        if not arr:
            return None
        
        max_sum = [0] * len(arr)
        max_sum_one_del = [0] * len(arr)
        
        max_sum[0] = arr[0]
        max_sum_one_del[0] = arr[0]
        
        for i in range(1, len(arr)):
            max_sum[i] = max(max_sum[i-1]+arr[i], arr[i])
            max_sum_one_del[i] = max(max_sum_one_del[i-1]+arr[i], arr[i])
            if i > 1:
                max_sum_one_del[i] = max(max_sum[i-2]+arr[i], max_sum_one_del[i])
                
        # print(max_sum)
        # print(max_sum_one_del)
            
        return max(max_sum_one_del)
            
        


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            
            if i >= 2:
                # first arg: the case where deletion occurs before i-1, or no deletion
                # second arg: the case where deletion is at i
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
                
        return max(max_ending_here1)

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        M = max(arr)
        if M<0:
            return M
        
        kad = arr[:]
        curr = 0
        for i in range(len(arr)):
            kad[i] = max(0, curr+kad[i])
            curr = kad[i]
        
        curr = 0
        revkad = arr[:]
        for i in range(len(arr)-1,-1,-1):
            revkad[i] = max(0, curr+revkad[i])
            curr = revkad[i]
        
        ans = max(kad)
        for i in range(1,len(arr)-1):
            ans = max(ans, kad[i-1]+revkad[i+1])
        
        
        return ans

class Solution:
     def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            if i >= 2:
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
        return max(max_ending_here1)
            


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        neg = []
        for i in range(len(arr)):
            if(arr[i]<0):
                neg.append(i)
        if(len(neg) == 0):
            return(sum(arr))
        if(len(neg) == len(arr) ):
            return max(arr)
        x1 = [0]*(len(neg))
        x2 = [0]*(len(neg))
        x1[0] = sum(arr[:neg[0]])
        x2[-1] = sum(arr[neg[-1]+1:])
        for j in range(1, len(neg)):
            for k in range(neg[j-1]+1, neg[j]):
                x1[j]+=arr[k]
            if(x1[j-1]+arr[neg[j-1]] > 0):
                x1[j]+=(x1[j-1]+arr[neg[j-1]])

        for j in range(len(neg)-2,-1,-1):
            for k in range(neg[j]+1,neg[j+1]):
                x2[j]+=arr[k]
            if(x2[j+1]+arr[neg[j+1]] > 0):
                x2[j]+=(x2[j+1]+arr[neg[j+1]])
        m = arr[0]
        for i in range(len(x1)):
            m = max(m, x1[i]+x2[i])
        return m

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            
            if i >= 2:
                # first arg: the case where deletion occurs before i-1, or no deletion
                # second arg: the case where deletion is at i
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
                
        return max(max_ending_here1)

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        bestFromS = [arr[0]]
        for i in range(1, len(arr)):
            bestFromS.append(max(arr[i], arr[i] + bestFromS[i - 1]))

        bestFromE = [0] * len(arr)
        bestFromE[len(arr) - 1] = arr[len(arr) - 1]
        for i in range(len(arr) - 2, -1, -1):
            bestFromE[i] = max(bestFromE[i + 1] + arr[i], arr[i])
        
        res = max(bestFromS)
        for i in range(len(arr)):
            before = 0 if i == 0 else bestFromS[i - 1]
            after = 0 if (i == len(arr) - 1) else bestFromE[i + 1]
            res = max(res, before + after)
        
        return res       


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        max1: int = arr[0]  # max subarray sum with at most one deletion
        max0: int = arr[0]  # max subarray sum with NO deletion
        res: int = arr[0]  # overall max to be returned
        for a in arr[1:]:
            max1 = max(max1 + a, max0, a)  # include a, not include a, or start with a
            max0 = max(max0 + a, a)  # update `max0`
            res = max(res, max1)  # update overall max
        return res

class Solution:
    def maximumSum(self, arr: List[int]) -> int:        
        if not arr:
            return None
        
        max_sum = [0] * len(arr)
        max_sum_one_del = [0] * len(arr)
        
        max_sum[0] = arr[0]
        max_sum_one_del[0] = arr[0]
        
        for i in range(1, len(arr)):
            max_sum[i] = max(max_sum[i-1]+arr[i], arr[i])
            max_sum_one_del[i] = max(max_sum_one_del[i-1]+arr[i], arr[i])
            if i > 1:
                max_sum_one_del[i] = max(max_sum[i-2]+arr[i], max_sum_one_del[i])
                
        print(max_sum)
        print(max_sum_one_del)
            
        return max(max_sum_one_del)
            
        


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if not arr:
            return 0
        if len(arr) == 1:
            return arr[0]
        
        fw = [arr[0]]
        bw = [arr[-1]]
        
        cur_max = max_so_far = arr[0]
        for num in arr[1:]:
            cur_max = max(cur_max + num, num)
            max_so_far = max(max_so_far, cur_max)
            fw.append(cur_max)
        
        cur_max = arr[-1]
        for num in arr[:-1][::-1]:
            cur_max = max(cur_max + num, num)
            max_so_far = max(max_so_far, cur_max)
            bw.append(cur_max)
        bw = bw[::-1]
        
        for i in range(1, len(arr) - 1):
            max_so_far = max(max_so_far, fw[i - 1] + bw[i + 1])
        return max_so_far

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        ans = -math.inf
        left = [-1] * n
        right = [-1] * n
        for i in range(n):
            left[i] = max(arr[i], left[i-1] + arr[i]) if i > 0 else arr[i]
            ans = max(ans, left[i])
        for i in range(n-1, -1, -1):
            right[i] = max(arr[i], right[i+1] + arr[i]) if i < n-1 else arr[i]
            ans = max(ans, right[i])
        for i in range(1, n-1):
            ans = max(ans, left[i-1]+right[i+1])
        return ans


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        dps = [elem for elem in arr] # dps[i] LCS starting at i
        dpe = [elem for elem in arr] # dpe[i] LCS ending at i
        dpt = [elem for elem in arr] # dpt[i] = dpe[i-1] + dps[i+1]
        for i in range(len(arr)):
            if i != 0:
                dpe[i] = max(dpe[i],dpe[i]+dpe[i-1])
                ip = len(arr) - i - 1
                dps[ip] = max(dps[ip],dps[ip]+dps[ip+1])
        for i in range(len(arr)):
            if i != 0 and i != len(arr) - 1:
                dpt[i] = dpe[i-1] + dps[i+1]
            elif i == 0:
                dpt[i] = dps[i+1]
            else:
                dpt[i] = dpe[i-1]
        # print(dps,dpe,dpt)
        return max(max(dpt),max(dpe),max(dps))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        s = sum(arr)
        pref = [0]
        
        for arr_i in arr:
            pref.append(pref[-1]+arr_i)
        
        for i in range(1, n+1):
            pref[i] = min(pref[i], pref[i-1])
        
        suf = [0]
        
        for arr_i in arr[::-1]:
            suf.append(suf[-1]+arr_i)
        
        for i in range(1, n+1):
            suf[i] = min(suf[i], suf[i-1])
        
        ans = s
        
        for i in range(n):
            if arr[i]<0:
                if i-1>=0:
                    ans = max(ans, s-arr[i]-pref[i-1]-suf[n-1-i])
                if n-2-i>=0:
                    ans = max(ans, s-arr[i]-pref[i]-suf[n-2-i])
        
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        # minimum size is > 1
        # do two array, positive and negative
        ans, dp1, dp2, lr, rl = -math.inf, [None] * len(arr), [None] * len(arr), 0, 0
        for i, val in enumerate(arr): 
            lr, rl = max(lr, 0) + val, max(rl, 0) + arr[len(arr)-1-i]
            dp1[i], dp2[len(arr)-1-i] = lr, rl
            ans = max(ans, lr, rl)
            
        for i in range(1, len(arr)-1): 
            if arr[i] < 0:
                ans = max(ans, dp1[i-1] + dp2[i+1])
        return ans
                
    # def maximumSum(self, arr: List[int]) -> int:
    #     n = len(arr)
    #     max_ending_here0 = n * [arr[0]]  # no deletion
    #     max_ending_here1 = n * [arr[0]]  # at most 1 deletion
    #     for i in range(1, n):
    #         max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
    #         max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
    #         if i >= 2:
    #             max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
    #     return max(max_ending_here1)
            


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        A = arr
        N = len(A)
        dp0 = [None] * N  # largest ending here
        dp1 = [None] * N  # largest starting here
        
        cur = A[0]
        dp0[0] = cur
        for i in range(1, N):
            cur = max(cur + A[i], A[i])
            dp0[i] = cur
        
        cur = A[-1]
        dp1[-1] = cur
        for i in range(N-2, -1, -1):
            cur = max(cur + A[i], A[i])
            dp1[i] = cur
        
        ans = max(dp0)
        for i, x in enumerate(A):
            if i+2 < N:
                ans = max(ans, dp0[i] + dp1[i+2])
        return ans


class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        n = len(nums)
        dp0 = [0 for i in range(n)]
        dp1 = [0 for i in range(n)]
        dp0[0] = nums[0]
        dp1[0] = nums[0]
        ans = nums[0]
        for i in range(1, n):
            dp0[i] = max(dp0[i-1]+nums[i], nums[i])
            dp1[i] = max(dp1[i-1]+nums[i], nums[i])
            if i > 1:
                dp1[i] = max(nums[i], dp1[i-1]+nums[i], nums[i]+dp0[i-2])
            ans = max(ans, dp0[i], dp1[i])
        return ans
            


import math
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [] 
        for i in range(n):
            dp.append([arr[i], arr[i]])
        for i in range(1, n):
            dp[i][0] = max(arr[i], dp[i - 1][0] + arr[i])    
            # print(dp[i][0]) 
            if i > 1:
                dp[i][1] = max(arr[i], dp[i-1][1]+arr[i],  dp[i-2][0]+arr[i])    
        ans = -math.inf
        for i in range(n):
            ans = max(ans, max(dp[i][0], dp[i][1]))
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        # Make a dp[n][2], where dp[i][0] is the largest sum of subarry ending at i without removing any element and dp[i][1] represents largest sum of subarray ending at i after removal of at most one element.
        
        n = len(arr)
        dp = [ [0 for _ in range(2)] for _ in range(n) ]
        dp[0] = [arr[0]] * 2
        for i in range(1, n):
            dp[i][0] = max(arr[i], dp[i-1][0] + arr[i])
            dp[i][1] = max(dp[i][0], dp[i-1][0], dp[i-1][1] + arr[i])     
        return max(map(lambda l: max(l), dp))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        res = float('-inf')
        max_ending_here0 = 3 * [arr[0]]  
        max_ending_here1 = 3 * [arr[0]]  
        for i in range(1, len(arr)):
            max_ending_here0[i%3] = max(max_ending_here0[(i-1)%3] + arr[i], arr[i])
            max_ending_here1[i%3] = max(max_ending_here1[(i-1)%3] + arr[i], arr[i])
            if i >= 2:
                max_ending_here1[i%3] = max(max_ending_here1[i%3], max_ending_here0[(i-2)%3] + arr[i])
            res = max(res, max_ending_here1[i%3])
        return res
            
            
            


import math
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        dp = [] 
        for i in range(n):
            dp.append([arr[i], arr[i]])
        for i in range(1, n):
            dp[i][0] = max(dp[i][0], dp[i - 1][0] + arr[i])    
            if i > 1:
                dp[i][1] = max(dp[i][1], max(dp[i-1][1]+arr[i], dp[i-2][0]+arr[i]))   
        ans = -math.inf
        for i in range(n):
            ans = max(ans, max(dp[i][0], dp[i][1]))
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        nodel=[arr[0]]
        for i in range(1,len(arr)):
            nodel.append(arr[i] + max(0, nodel[i-1]))
        onedel=[arr[0]]
        for i in range(1, len(arr)):
            onedel.append(max(nodel[i], nodel[i-1],arr[i]+onedel[-1]))
        return max(onedel)    
            


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        mx,n = float('-inf'),len(arr)
        left,right = [float('-inf') for _ in range(len(arr))],[float('-inf') for _ in range(len(arr))]
        for i in range(len(arr)):  
            left[i] = max(arr[i],arr[i] + left[i-1]) if i > 0 else arr[0]
            right[n-i-1] = max(arr[n-i-1],arr[n-i-1] + right[n-i]) if i > 0 else arr[-1]
            
        for i in range(len(arr)):
            mx = max(mx, arr[i])
            if 2*arr[i] != left[i] + right[i]:
                mx = max(mx, left[i] + right[i] - 2*arr[i])
        return mx
            
        
        
            
        
        
        


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr)==1:
            return arr[0]
        dp=[[0]*2 for i in range(len(arr))]
        dp[0][0]=arr[0]
        for i in range(1,len(arr)):
            dp[i][0]=max(arr[i],dp[i-1][0]+arr[i])
            dp[i][1]=max(dp[i-1][1]+arr[i],dp[i-1][0])
        ans=float('-inf')
        for i in range(len(arr)):
            ans=max(ans,dp[i][0],dp[i][1])
        if ans==0:
            return max(arr)
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        max_res = [0] * len(arr)
        max_start = [0] * len(arr)
        max_end = [0] * len(arr)
        
        for i, n in enumerate(arr):
            max_end[i] = n if i == 0 else max(n, max_end[i-1] + n)
        print(max_end)
        
        for i, n in list(enumerate(arr))[::-1]:
            max_start[i] = n if i == len(arr) - 1 else max(n, max_start[i+1] + n)
        print(max_start)
            
        for i, n in enumerate(arr):
            max_left = n if i == 0 else max_end[i-1]
            max_right = n if i == len(arr) - 1 else max_start[i+1]
            max_res[i] = max(max_left, max_right, max_left + max_right)
        print(max_res)
        
        return max(max_res)

class Solution:
    def maximumSum(self, a: List[int]) -> int:
        max_so_far = -sys.maxsize
        max_ending_here = 0
        size=len(a)
        dp=[-sys.maxsize]*size
        dp[0]=a[0]
        dp1=[-sys.maxsize]*size
        dp1[0]=a[0]
        for i in range(1, size): 
            dp[i]=max(a[i],dp[i-1]+a[i])
            dp1[i]=max(a[i],dp1[i-1]+a[i])
            if i>=2:
                dp1[i]=max(dp1[i],dp[i-2]+a[i])
        return max(dp1)
        


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        # Make a dp[n][2], where dp[i][0] is the largest sum of subarry ending at i without removing any element and dp[i][1] represents largest sum of subarray ending at i after removal of one element.
        
        n = len(arr)
        dp = [ [0 for _ in range(2)] for _ in range(n) ]
        dp[0] = [arr[0]] * 2
        for i in range(1, n):
            dp[i][0] = max(arr[i], dp[i-1][0] + arr[i])
            dp[i][1] = max(dp[i][0], dp[i-1][1] + arr[i])
            if i >= 2:
                dp[i][1] = max(dp[i][1], dp[i-2][0] + arr[i])     
        return max(map(lambda l: max(l), dp))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        dp = [[0 for _ in range(2)] for _ in range(len(arr))]
        dp[0][0] = arr[0]
        dp[0][1] = arr[0]
        
        ans = max(dp[0])
        for i in range(1, len(arr)):
            dp[i][0] = max(dp[i-1][0] + arr[i], dp[i-1][1])
            dp[i][1] = max(dp[i-1][1] + arr[i], arr[i])

            ans = max(ans, dp[i][0], dp[i][1])
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        # dp[i][k] is the maximum subarray up to arr[i] with k deletions, ending at arr[i]
        # 0 no deletion happens, 1 deletion
        n = len(arr)
        dp = [[float('-inf')]*2 for _ in range(n) ]
        dp[0][0] = arr[0]
        dp[0][1] = float('-inf')  # it cannot be zero since no empty subarray
        
        for i in range(1,n):
            dp[i][0] = max(arr[i],dp[i-1][0]+arr[i])
            dp[i][1] = max(dp[i-1][1]+arr[i], dp[i-1][0] )
        ans = float('-inf')
        for i in range(n):
            for j in range(2):
                ans = max(ans,dp[i][j])
                
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        #s[i, 0] = max sum so far up to (including) i-th num without deletion of num at position i
        #s[i, 0] = max sum so far up to (including) i-th num with deletion of num at position i
        #s[i, 0] = max(s[i-1, 0], 0) + arr[i]
        #s[i, 1] = max(max(s[i-1, 1], 0) + arr[i], s[i-1][0])
        # max(all of s elements)
        if len(arr)==1:
            return arr[0]
        ans = arr[0]
        n = len(arr)
        s = []
        for i in range(n):
            s.append([None, None])
        s[0][0] = s[0][1] = arr[0]
        for i in range(1, n):
            s[i][0] = max(s[i-1][0], 0) + arr[i]
            s[i][1] = max(max(s[i-1][1], 0) + arr[i], s[i-1][0])
            ans = max(s[i][0], s[i][1], ans)
        print(s)
        return ans
            
            
            


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        
        r = max(arr)
        if r < 0:
            return r
        
        l = len(arr)
        f = [0]*l
        b = [0]*l
        
        cur = 0
        
        for i in range(l):
            f[i] = cur
            cur += arr[i]
            cur = max(cur, 0)

        cur = 0
        for i in range(l-1, -1, -1):
            b[i] = cur
            cur += arr[i]
            cur = max(cur, 0)

        return max(f[i]+b[i] for i in range(l))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        max_overall = arr[0]
        max_sum = arr[0]
        max_excluded = float('-inf')
        for i in range(1, len(arr)):
            max_excluded = max(max_excluded + arr[i], max_sum)
            max_sum = max(max_sum + arr[i], arr[i])
            max_overall = max(max_overall, max_sum, max_excluded)
        return max_overall


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        curr_max = [-math.inf, -math.inf]
        max_sum = -math.inf
        for num in arr:
            curr_max[0], curr_max[1] = max(num, curr_max[0] + num), max(curr_max[1] + num, curr_max[0])
            max_sum = max([max_sum, curr_max[0], curr_max[1]])
        
        return max_sum

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            if i >= 2:
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
        return max(max_ending_here1)

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        positive = [0 for _ in range(len(arr))]
        negative = positive.copy()
        positive[0] = arr[0]
        for i, num in enumerate(arr[1:]):
            positive[i+1] = max(num, positive[i] + num)
            negative[i+1] = max(negative[i] + num, positive[i])
        return max(positive+negative[1:])
            


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        
        @lru_cache(None)
        def max_sum_start_at(i):
            if i == len(arr) - 1:
                return arr[-1]
            return max(arr[i], arr[i] + max_sum_start_at(i + 1))
        
        @lru_cache(None)
        def max_sum_end_at(j):
            if j == 0:
                return arr[0]
            
            return max(arr[j], arr[j] + max_sum_end_at(j - 1))
        
        return max(max([max_sum_start_at(i) for i in range(len(arr))]), 
                   max([max_sum_end_at(i - 1) + max_sum_start_at(i + 1) for i in range(1, len(arr) - 1)]))

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if max(arr) < 0:
            return max(arr)
        
        @lru_cache(maxsize=None)
        def recurse(idx, isSkipped):
            if idx == len(arr):
                return 0
            
            if isSkipped:
                return max(arr[idx] + recurse(idx + 1, True), 0)
            else:
                return max(arr[idx] + recurse(idx + 1, False), recurse(idx + 1, True), arr[idx])
                
            # return memo[(idx, isSkipped)]
        
        curMax = float('-inf')
        for i in range(len(arr)):
            curMax = max(recurse(i, False), curMax)

        return curMax

class Solution:
  def maximumSum(self, arr: List[int]) -> int:
    max0, max1, result = arr[0], arr[0], arr[0]
    for n in arr[1:]:
      max1 = max(max1 + n, max0, n)
      max0 = max(max0 + n, n)
      result = max(result, max1)
    return result

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        dp=[[0]*2 for i in range(len(arr))]
        if len(arr)==0:
            return 0
        
        dp[0][0]=arr[0]
        dp[0][0]=arr[0]
        maxm=arr[0]
        
        for i in range(1,len(arr)):
            dp[i][0]=max(dp[i-1][0]+arr[i],arr[i])
            dp[i][1]=max(arr[i],dp[i-1][1]+arr[i],dp[i-1][0])
            
            maxm=max(maxm,dp[i][0],dp[i][1])
            
        return maxm
                


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        dp = [[0 for _ in range(2)] for _ in range(len(arr))]
        mins = [0 for _ in range(len(arr))]
        # dp[0][0] = max(0, arr[0])
        dp[0][0] = arr[0]
        dp[0][1] = arr[0]
        mins[0] = arr[0]
        
        ans = max(dp[0])
        for i in range(1, len(arr)):
            if arr[i] >= 0:
                if dp[i-1][0] < 0:
                    dp[i][0] = arr[i]
                    dp[i][1] = arr[i]
                    mins[i] = arr[i]
                else:
                    dp[i][0] = dp[i-1][0] + arr[i] 
                    dp[i][1] = max(dp[i-1][1] + arr[i], arr[i])
                    mins[i] = min(mins[i-1], arr[i])
            else:
                if dp[i-1][0] < 0:
                    dp[i][0] = arr[i]
                    dp[i][1] = arr[i]
                    mins[i] = arr[i]
                else:
                    mins[i] = min(mins[i-1], arr[i])
                    dp[i][0] = max(dp[i-1][0] + arr[i], dp[i-1][1])
                    dp[i][1] = max(dp[i-1][1] + arr[i], arr[i])

            ans = max(ans, dp[i][0], dp[i][1])
        return ans

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        maxi=nums[0]
        sumi=nums[0]
        left=[nums[0]]
        right=[nums[-1]]
        for i in nums[1:]:
            sumi=max(i,sumi+i)
            left.append(sumi)
        t=nums[::-1]
        sumi=t[0]
        for i in t[1:]:
            sumi=max(i,sumi+i)
            right.append(sumi)
        right=right[::-1]
        l=len(nums)
        res=0
        # print(left)
        # print(right)
        for i in range(l):
            res=max(res,(left[i]+right[i]-(2*nums[i])))
        if res!=0:return res
        return max(nums)


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0]
        maxsum = [0]
        for i in reversed(range(1, n)):
            if maxsum[-1] > 0:
                maxsum.append(maxsum[-1] + arr[i])
            else:
                maxsum.append(arr[i])
        s = 0
        result = -10 ** 6
        for i, a in enumerate(arr):
            r = maxsum.pop()
            if 0 < i < n - 1:
                result = max(result, s + r)
            if s > 0:
                s += a
            else:
                s = a
            result = max(result, s)
        return result

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if not arr:
            return 0
        max_del = arr[0]
        max_no_del = arr[0]
        res = arr[0]
        
        for i in range(1, len(arr)):
            max_del = max(max_del + arr[i], max_no_del, arr[i])
            max_no_del = max(max_no_del + arr[i], arr[i])
            res = max(res, max_del)
        
        return res

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        #if len(arr) == 1:
        #    return arr[0]
        nodel, delected = 0, 0
        res = float('-inf')
        for num in arr:
            delected = max(nodel, delected + num)
            nodel = max(nodel, 0) + num
            res = max(nodel, delected, res)
        return res
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        nodel, delected = arr[0], 0
        res = arr[0]
        for num in arr[1:]:
            delected = max(nodel, delected + num)
            nodel = max(nodel, 0) + num
            res = max(nodel, delected, res)
        return res

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        max_ending_here0 = n * [arr[0]]  # no deletion
        max_ending_here1 = n * [arr[0]]  # at most 1 deletion
        for i in range(1, n):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i])
            max_ending_here1[i] = max(max_ending_here1[i-1] + arr[i], arr[i])
            if i >= 2:
                max_ending_here1[i] = max(max_ending_here1[i], max_ending_here0[i-2] + arr[i])
        return max(max_ending_here1)
            
            
                
        
        
        
        


class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        n = len(arr)
        dp0, dp1, res = arr[0], 0, arr[0]
        for i in range(1,n):
            dp0, dp1 = max(dp0+arr[i], arr[i]), max(dp0,dp1+arr[i])
            res = max(dp0, dp1, res)
        return res

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr)==1:
            return arr[0]
        
        def helper(arr):
            n=len(arr)
            dp=[0]*n

            if arr==[]:
                return 0
            else:
                res=0
                curr=arr[0]
                dp[0]=arr[0]
                for i in range(1,len(arr)):

                    
                    curr=max(curr+arr[i],arr[i])
                   
                    
                    res=max(res,curr)
                    dp[i]=curr
                    # print(res)
                return dp,res
            
        lp,best=helper(arr)
        rp,best=helper(arr[::-1])
        rp=rp[::-1]
            
        print(lp,rp)

        ans=-1
        for k in range(0,len(arr)):
            
            val=rp[k+1] if k<len(arr)-1 else 0 
            val2=lp[k-1]  if k>0 else 0
            print(val2,val)
            ans=max(ans,best,val+val2,val,val2)
        if ans==0:
            return -1
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if max(arr) < 0:
            return max(arr)
        
        memo = {}
        def recurse(idx, isSkipped):
            if idx == len(arr):
                return 0
            
            if (idx, isSkipped) in memo:
                return memo[(idx, isSkipped)]
            
            if isSkipped:
                memo[(idx, isSkipped)] = max(arr[idx] + recurse(idx + 1, True), 0)
            else:
                memo[(idx, isSkipped)] = max(arr[idx] + recurse(idx + 1, False), recurse(idx + 1, True), arr[idx])
                
            return memo[(idx, isSkipped)]
        
        curMax = float('-inf')
        for i in range(len(arr)):
            curMax = max(recurse(i, False), curMax)

        return curMax

class Solution:       
    def maximumSum(self,a: List[int]) -> int:
        n=len(a)
        ans=skipped=not_skipped=a[-1]
        for i in range(n-2,-1,-1):
            not_skipped,skipped=max(a[i],a[i]+not_skipped,skipped),max(a[i],a[i]+skipped)
            ans=max(ans,skipped,not_skipped)
        return ans

class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        if len(arr) == 1:
            return arr[0]
        
        N = len(arr)
        
        max_ending_here0 = [0] * N
        max_ending_here1 = [0] * N
        
        max_ending_here0[0] = arr[0]
        max_ending_here1[0] = arr[0]
        
        max_ending_here0[1] = max(max_ending_here0[0] + arr[1], arr[1]) 
        max_ending_here1[1] = max(max_ending_here1[0] + arr[1], arr[1])
        
        for i in range(2, N):
            max_ending_here0[i] = max(max_ending_here0[i-1] + arr[i], arr[i]) 
            max_ending_here1[i] = max(
                max_ending_here1[i-1] + arr[i], 
                max_ending_here0[i-2] + arr[i], 
                arr[i])
            
        #print(max_ending_here0)
        #print(max_ending_here1)
           
        return max(max_ending_here1)