C++,Kadane Algo, Dynamic Programming
\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int ans = -1e9;\n        int n = arr.size();\n        // dp1[i] -> max sum ending a
```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int ans = -1e9;\n        int n = arr.size();\n        // dp1[i] -> max sum ending at i starting from index 0\n        int dp1[n];\n        // dp2[i] -> max sum starting at index i \n        int dp2[n];\n        if(n == 1){\n            return arr[0];\n        }\n         dp1[0] = arr[0];\n        for(int i=1;i<n;i++){\n            // either keep only this value or extend with previous index\n            dp1[i] = max(arr[i],arr[i]+dp1[i-1]);\n        }\n         dp2[n-1] = arr[n-1];\n        for(int i=n-2;i>=0;i--){\n            // either keep only this value or extend with next index\n            dp2[i] = max(arr[i],arr[i]+dp2[i+1]);\n        }\n        for(int i=1;i<n-1;i++){\n            int temp;\n            if(dp1[i-1]>=0 && dp2[i+1]>=0){\n                temp = dp1[i-1]+dp2[i+1];\n            }\n            else{\n                temp = max(dp1[i-1],dp2[i+1]);\n            }\n            // dont remove if its positive\n            if(arr[i]>0) temp+=arr[i];\n            ans = max(ans,temp);\n        }\n        ans = max(ans,dp2[1]); // when removing 0th index\n        ans = max(ans,dp1[n-2]); // when removing n-1 th index\n        return ans;\n    }\n};\n```
['Dynamic Programming']