C++ Solution using DP and Kadane's Algorithm
\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size(), curr, maxi = INT_MIN;\n        vector<int> fw(n + 1, 0), bw(n +
```\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int n = arr.size(), curr, maxi = INT_MIN;\n        vector<int> fw(n + 1, 0), bw(n + 1, 0);\n        fw[0] = arr[0];\n        maxi = max(maxi, fw[0]);\n        \n\t\t// ith element denotes the maximum subarray sum with ith element as the last element\n        for(int i = 1; i < n; ++i) {\n            curr = max(arr[i], fw[i - 1] + arr[i]);\n            maxi = max(maxi, curr);\n            fw[i] = curr;\n        }\n        \n\t\t// similar to fw array, but in the backward direction\n        bw[n - 1] = curr = arr[n - 1];\n        for(int i = n - 2; i >= 0; --i) {\n            curr = max(arr[i], bw[i + 1] + arr[i]);\n            maxi = max(maxi, curr);\n            bw[i] = curr;\n        }\n        \n        int res = INT_MIN;\n        for(int i = 1; i < n - 1; ++i) {\n            res = max(res, fw[i - 1] + bw[i + 1]);\n        }\n        return max(res, maxi);\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']