[C++/Java/Python] Dynamic programing solution with clear explanation
We use int[] dp = new int[2] to denote the current state. As we access the element in the array, dp[0] means the maximum subarray sum without one deletion while
We use int[] dp = new int[2] to denote the current state. As we access the element in the array, dp[0] means the maximum subarray sum without one deletion while dp[1] signifies the maximum subarray sum with one deletion. Obviously, **dp[1] <- max(dp[0], dp[1] + arr[i])**, which enumerates two possible scenarios: **(1) We delete the current element; (2) We delete one element to the left of the current element.** In this way, we get the solution with time complexity **O(N)** and space complexity **O(1)**. \n\n**C++**\n```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size();\n        if (n == 1)\n            return arr[0];\n        int dp[2] = {arr[0], 0};\n        int res = arr[0];\n        for (int i = 1; i < n; i++) {\n            dp[1] = max(dp[0], dp[1]+arr[i]);\n            dp[0] = max(arr[i], dp[0]+arr[i]);\n            res = max(res, max(dp[0], dp[1]));\n        }\n        return res;\n    }\n};\n```\n\n**Java**\n```\nclass Solution {\n    public int maximumSum(int[] arr) {\n        int n = arr.length;\n        if (n == 1)\n            return arr[0];\n        int[] dp = {arr[0], 0};\n        int res = arr[0];\n        for (int i = 1; i < n; i++) {\n            dp[1] = Math.max(dp[0], dp[1]+arr[i]);\n            dp[0] = Math.max(arr[i], dp[0]+arr[i]);\n            res = Math.max(res, Math.max(dp[0], dp[1]));\n        }\n        return res;\n    }\n}\n```\n\n**Python**\n```\nclass Solution(object):\n    def maximumSum(self, arr):\n        dp, res = [arr[0], 0], arr[0]\n        for i in range(1, len(arr)):\n            dp[1] = max(dp[0], dp[1]+arr[i])\n            dp[0] = max(arr[i], arr[i]+dp[0])\n            res = max(res, dp[0], dp[1])\n        return res\n```\n
[]