Java, DP, O(n), Beat 100%, detail explanation
It is easy to calculate the max subarray sum using DP.\nThis problem is like a follow up to the max subarray problem.\nThere are two case in the final result:\n
It is easy to calculate the max subarray sum using DP.\nThis problem is like a follow up to the max subarray problem.\nThere are two case in the final result:\n* case 1, we don\'t delete anything, which can be solved by max subarray problem\n* case 2, we only delete one element.\n\nAnd There is one fact we need to know first:\n* If we delete one element from array, this element must be a negative one. Why? because if we delete a positive one, it can be added back and make the sum larger.\n\nTherefore, we only need to check negative number in the final loop. \nWe need two dp array, dp1 to store the max subarray ended with positive i. dp2 to store max subarray started at positive i.\nSo the max sum of deleting arr[i] is dp[i-1] + dp[i+1].\n\n```\nclass Solution {\n    public int maximumSum(int[] arr) {\n        if(arr.length == 1) return arr[0];\n        int n = arr.length;\n        int[] dp1 = new int[n];\n        int[] dp2 = new int[n];\n        \n        dp1[0] = arr[0];\n        dp2[n-1] = arr[n-1];\n        int max = arr[0];\n        \n        for(int i=1; i<n; i++){\n            dp1[i] = dp1[i-1] > 0 ? dp1[i-1] + arr[i] : arr[i];\n            max = Math.max(max, dp1[i]);\n        }\n        for(int i=n-2; i>=0; i--){\n            dp2[i] = dp2[i+1] > 0 ? dp2[i+1] + arr[i] : arr[i];\n        }\n        \n        for(int i=1; i<n-1; i++){ \n            if(arr[i] < 0){\n                max = Math.max(max, dp1[i-1] + dp2[i+1]); \n            }\n        }\n        return max;\n    }\n}\n```\n
[]