Python DP Solution with Explanation
Define dp(i, d) as maximum subarray sum on arr[:i + 1] with d times deletions.\nWe\'ll get this recursion: \ndp(i, 0) = max(arr[i], dp(i - 1, 0) + arr[i])\ndp(i
Define `dp(i, d)` as maximum subarray sum on `arr[:i + 1]` with `d` times deletions.\nWe\'ll get this recursion: \n`dp(i, 0) = max(arr[i], dp(i - 1, 0) + arr[i])`\n`dp(i, 1) = max(dp(i - 1, 0), dp(i - 1, 1) + arr[i])`.\n\n```python\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        n = len(arr)\n        dp = [[float(\'-inf\')] * 2 for _ in range(n)]\n        res = float(\'-inf\')\n        for i, a in enumerate(arr):\n            dp[i][0] = max(a, dp[i - 1][0] + a)\n            dp[i][1] = max(dp[i - 1][0], dp[i - 1][1] + a)\n            res = max(res, *dp[i])\n        return res\n```\n\nIn the recursion above, we can forget `dp(i - 1, 0)` and `dp(i - 1, 1)` after we compute `dp(i, 0)` and `dp(i, 1)`. So we can solve this problem by constant space.\n\n```python\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        x = y = res = float(\'-inf\')\n        for a in arr:\n            x, y = max(a, x + a), max(x, y + a)\n            res = max(res, x, y)\n        return res\n```
['Dynamic Programming', 'Python', 'Python3']