[C++] Forward and backward, O(n) solution
\n    int maximumSum(vector<int>& arr) {\n        int n=arr.size();\n        vector<int> fw(n,0);\n        vector<int> bw(n,0);\n        int cur_max=arr[0],max_
```\n    int maximumSum(vector<int>& arr) {\n        int n=arr.size();\n        vector<int> fw(n,0);\n        vector<int> bw(n,0);\n        int cur_max=arr[0],max_so_far=arr[0];\n        fw[0]=arr[0];\n        for(int i=1;i<n;i++){\n            cur_max=max(arr[i],cur_max+arr[i]);\n            max_so_far=max(max_so_far,cur_max);\n            fw[i]=cur_max;\n        }\n        cur_max=max_so_far=bw[n-1]=arr[n-1];\n        for(int i=n-2;i>=0;i--){\n            cur_max=max(arr[i],cur_max+arr[i]);\n            max_so_far=max(max_so_far,cur_max);\n            bw[i]=cur_max;\n        }\n        int res=max_so_far;\n        for(int i=1;i<n-1;i++)\n            res=max(res,fw[i-1]+bw[i+1]);\n        return res;\n    }\n```
[]