Clean Python Solution (Self-Explained, With Other Similar Problems)
python\nclass Solution(object):\n    def maximumSum(self, arr):\n        if not arr: return arr\n        if len(arr)==1: return arr[0]\n        \n        dp = [
```python\nclass Solution(object):\n    def maximumSum(self, arr):\n        if not arr: return arr\n        if len(arr)==1: return arr[0]\n        \n        dp = [[0, 0] for _ in xrange(len(arr))]\n        subarrayMaxSum = arr[0]\n        \n        for i in xrange(len(arr)):\n            if i==0:\n                dp[i][0] = arr[i]\n                dp[i][1] = arr[i]\n            else:\n                dp[i][0] = max(dp[i-1][0]+arr[i], arr[i])\n                dp[i][1] = max(dp[i-1][0], dp[i-1][1]+arr[i], arr[i])\n            subarrayMaxSum = max(subarrayMaxSum, dp[i][0], dp[i][1])\n        \n        return subarrayMaxSum\n\n"""\ndp[i][0] = max sum that ends at arr[i], not yet done any deletion\ndp[i][1] = max sum that ends at arr[i], already done the deletion\n\ndp[i][0] = max(dp[i-1][0]+arr[i], arr[i])\ndp[i][1] = max(dp[i-1][0], dp[i-1][1]+arr[i], arr[i])\n\nTime: O(N).\nSpace: O(N), can further reduce to O(1).\n"""\n\n"""\nSimilar Problems: 1289, 123\nFor more other topics similar problems, check out my GitHub.\nIt took me a lots of time to make the solution. Becuase I want to help others like me.\nPlease give me a star if you like it. Means a lot to me.\nhttps://github.com/wuduhren/leetcode-python\n"""\n```
[]