Intuitive Java Solution With Explanation
Idea\nCompute maxEndHere and maxStartHere arrays and also find overall max along with them.\nNow, evaluate the case where 1-element can be eliminated, that is a
**Idea**\nCompute `maxEndHere` and `maxStartHere` arrays and also find overall `max` along with them.\nNow, evaluate the case where 1-element can be eliminated, that is at each index, we can make use of `maxEndHere[i-1]+maxStartHere[i+1]`\n\n**Thought process**\nThis approach is a slight improvisation on the idea of https://leetcode.com/problems/maximum-subarray/. Basically, the difference here is we can eliminate 1 number and still can continue with expanding our subarray. So imagine a subarray where you removed 1 element, then it forms two subarrays ending at prev index and starting at next index. We know how to get `maxEndHere` from the max sum subarray problem for each index. If we reverse our thinking to follow the same logic to solve for subarray at next index, we should be able to see computing `maxStartHere` is just backwards of `maxEndHere`. So now at each index, it is just about looking at prev and next numbers from the respective arrays to get overall `max`.\n\n```\npublic int maximumSum(int[] a) {\n        int n = a.length;\n        int[] maxEndHere = new int[n], maxStartHere = new int[n];\n        int max = a[0];\n        maxEndHere[0] = a[0];\n        for(int i=1; i < n; i++){\n            maxEndHere[i] = Math.max(a[i], maxEndHere[i-1]+a[i]);\n            max = Math.max(max, maxEndHere[i]);\n        }\n        maxStartHere[n-1] = a[n-1];\n        for(int i=n-2; i >= 0; i--)\n            maxStartHere[i] = Math.max(a[i], maxStartHere[i+1]+a[i]);\n        for(int i=1; i < n-1; i++)\n            max = Math.max(max, maxEndHere[i-1]+maxStartHere[i+1]);\n        return max;\n    }\n```
[]