Python O(N), S(N) 3-pass solution with clear comments
This problem can be easily solved by Brute Force. However, Brute Force has TLE problem. Thus we need an optimal algorithm.\n\nBasic idea of my algorithm is, we 
This problem can be easily solved by Brute Force. However, Brute Force has TLE problem. Thus we need an optimal algorithm.\n\nBasic idea of my algorithm is, we need to maintain 2 dp array, one is dp_ends_at_i, i.e., maximum subarray ends at index i, which goes from left to right, and dp_starts_from_i, i.e., maximum subarray starts from index i, which goes from left to right, too.\n\nFirst pass, we need to get the dp_ends_at_i, which is a classical DP problem. In this pass the global maximum subarray without any deletion is obtained.\n\nSecond pass, we start from the right to left and get the dp_starts_from_i.\n\nThird pass, we delete each element in the array one by one. Whenever we delete a number, say, arr[i], we need to check the maximum subarray in arr[0,1,...,i-1], right maximum subarray in arr[i+1, i+2, ..., len(arr)-1], and the cross maximum subarry in arr[0,1,...,i-1,i+1,...,len(arr)-1], which can be easily obtained by combining dp_ends_at_i and dp_starts_from_i. Note that we should be careful when handling the corner case.\n\nO(N), S(N)\n\n```\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        dp_ends_at_i = [0] * len(arr)\n        dp_starts_from_i = [0] * len(arr)\n        \n        no_del = arr[0]\n        dp_ends_at_i[0] = arr[0]\n        for i in range(1, len(arr)):\n            dp_ends_at_i[i] = max(dp_ends_at_i[i-1] + arr[i], arr[i])\n            no_del = max(dp_ends_at_i[i], no_del)\n\n        result = no_del\n        \n        dp_starts_from_i[-1] = arr[-1]\n        for i in range(len(arr)-2, -1, -1):\n            dp_starts_from_i[i] = max(dp_starts_from_i[i+1]+arr[i], arr[i])\n        \n        for i in range(0, len(arr)):\n            left = float("-inf") if i == 0 else dp_ends_at_i[i-1]\n            right = float("-inf") if i == len(arr) - 1 else dp_starts_from_i[i+1]\n            cross = left + right\n            result = max(result, max(max(left, right), cross))\n        \n        return result\n            \n```\n
['Dynamic Programming', 'Python']