Clean and Short Solution with Explanation
Idea?\n We have to delete atmost one element.\n Find the maximum subarray sum when none of the elements are deleted using Kadane\'s Algorithm.\n Now, we have n 
**Idea?**\n* We have to delete **atmost one element**.\n* Find the maximum subarray sum when none of the elements are deleted using *Kadane\'s Algorithm*.\n* Now, we have **n choices** to delete an element.\n* We\'ll **consider every index i** and delete the element present at that index and find the maximum subarray sum we can get.\n* Say, If we **delete the current element at index i**, we can find current maximum subarray sum due to deleting this element, if we know the **maximum subarray sum ending at index i-1** as well as **i+1** from **prefix as well as suffix side** respectively.\n* Check commented Code below to know more.\n```\nclass Solution {\npublic:\n    // Time Complexity:- O(N)\n    // Space Complexity:- O(N)\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size();\n\n        // base case\n        if(n==1){\n            return arr.back();\n        }\n\n        // find maximum subarray sum when no element is deleted using kadane\'s algorithm\n        int ans = arr[0],currmax = arr[0];\n        for(int i=1;i<n;i++){\n            currmax = max(currmax+arr[i],arr[i]);\n            ans = max(ans,currmax);\n        }\n\n        // pref[i] = maximum subarray sum ending at index i from front side\n        vector<int> pref(n),suff(n);\n        for(int i=0;i<n;i++){\n            pref[i] = arr[i];\n            if(i>0){\n                pref[i] = max(pref[i],pref[i]+pref[i-1]);\n            }\n        }\n\n        // suff[i] = maximum subarray sum ending at index i from backside\n        for(int i=n-1;i>=0;i--){\n            suff[i] = arr[i];\n            if(i+1<n){\n                suff[i] = max(suff[i],suff[i]+suff[i+1]);\n            }\n        }\n\n        for(int i=0;i<n;i++){\n            // delete the arr[i] and find the current maximum subarray sum\n            vector<int> curr;\n\n            // curr vector stores possible left and right maximum subarray sums\n            if(i+1<n){\n                curr.push_back(suff[i+1]);\n            }\n\n            if(i-1>=0){\n                curr.push_back(pref[i-1]);\n            }\n\n            // if curr size is 1, there is only 1 operation, we have to choose that value\n            if(curr.size()==1){\n                ans = max(ans,curr.back());\n            }\n            else{\n                //  here we can choose 3 values\n                // a, b, a+b\n                ans = max({ans,curr[0],curr[1],curr[0]+curr[1]});\n            }\n        }\n\n        return ans;\n    }\n};\n```
[]