[Python] O(N) time O(1) space one pass DP solution
One pass O(N) space solution:\n\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        n = len(arr)\n        dp1 = n * [float(\'-inf\')] #d
One pass O(N) space solution:\n```\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        n = len(arr)\n        dp1 = n * [float(\'-inf\')] #dp1[i] the maximum sum of the subarray that ends at ith index and have deleted one element.\n        dp2 = n * [float(\'-inf\')] # dp2[i] the maximum sum of the subarray that ends at ith index and does not delete one element.\n        dp2[0] = arr[0]\n        res = arr[0]\n        for i in range(1,n):\n            dp1[i] = max(dp1[i-1] + arr[i],dp2[i-1]) \n            dp2[i] = max(dp2[i-1] + arr[i],arr[i])\n            res = max(res,dp1[i],dp2[i])\n        return res\n```\n\nOne pass O(1) space solution:\n```\nclass Solution:\n    def maximumSum(self, arr: List[int]) -> int:\n        n = len(arr)\n        dp1,dp2,res = float(\'-inf\'),arr[0],arr[0]\n        for i in range(1,n):\n            dp1,dp2= max(dp1+ arr[i],dp2),max(dp2 + arr[i],arr[i])\n            res = max(res,dp1,dp2)\n        return res\n```\n
['Dynamic Programming', 'Python']