[Python] One pass, O(1) Space
python\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        max1: int = arr[0]  # max subarray sum with at most one deletion\n        max
```python\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        max1: int = arr[0]  # max subarray sum with at most one deletion\n        max0: int = arr[0]  # max subarray sum with NO deletion\n        res: int = arr[0]  # overall max to be returned\n        for a in arr[1:]:\n            max1 = max(max1 + a, max0, a)  # include a, not include a, or start with a\n            max0 = max(max0 + a, a)  # update `max0`\n            res = max(res, max1)  # update overall max\n        return res\n```\nExplanation:\nFor element arr[i], `max0` is the max subarray sum ending at arr[i - 1] with no deletion; `max1` is the max subarray sum ending at arr[i - 1] with at most one deletion; `res` is the overall max to be returned at the end. For each arr[i], we consider a new `max1`. There are three situations:\n1. ~~Use the previous max1. Since there must have been at most one element deleted, arr[i] cannot be removed.~~ So `max1 = max1 + arr[i]`\n2. Delete arr[i]. Then the new `max1` must be the same as the previous\n`max0`, i.e. `max1 = max0`\n3. arr[i] is so big that it is better to start from it, i.e. `max1 = arr[i]`\n\nWe pick the largest among the three situations to be the new `max1`. And keep updating `max0` and `res`.\n\nEdit:\nThanks to @abhigenie92 for pointing out that the description of using `max1` and arr[i] is not correct. It should be like this: Use arr[i] with some previous sum ending at arr[i -1]. This previous sum has to be `max1`, because using `max0` would miss the situation where some element has been deleted.
[]