[Java] One pass DP solution, O(n)  time and O(1) space
At each step we maintain the largest value of a subarray that has one element deleted and has no elements deleted.\n2. Current value of the subarray with no ele
1. At each step we maintain the largest value of a subarray that has one element deleted and has no elements deleted.\n2. Current value of the subarray with no elements deleted is: max(current value, full subarray + current value)\n3. Current value of the subarray with one element deleted is: max(previous full subarray and we are not including current value, previous subarray with one element deleted plus current value)\n\n\n```\nclass Solution {\n    public int maximumSum(int[] arr) {\n        int n = arr.length;\n\t\t\n        int prevFull = arr[0];\n        int prevGap = -Math.abs(arr[0]);        \n        int max = arr[0];\n\t\t\n        for (int i=1; i<n; i++) {\n            int curFull = Math.max(arr[i], prevFull + arr[i]);            \n            int curGap = Math.max(prevFull, prevGap + arr[i]);\n            \n            max = Math.max(max, Math.max(curFull, curGap));\n            \n            prevFull = curFull;\n            prevGap = curGap;\n        }\n        \n        return max;\n    }\n}\n```
[]