C++ forward and backward solution with explanation and picture
This problem is kind a modifiled version from Kenede\'s algorithm. see here\n We calculate the maximum subarray sum foward and backward\n Picture below shows ho
* This problem is kind a modifiled version from Kenede\'s algorithm. see [here](https://en.wikipedia.org/wiki/Maximum_subarray_problem)\n* We calculate the maximum subarray sum foward and backward\n* Picture below shows how it goes\n![image](https://assets.leetcode.com/users/bug_exceeded/image_1567920728.png)\n\n```cpp\nclass Solution \n{\npublic:\n    int maximumSum(vector<int>& v) \n    {\n        int res = 0, n = v.size();\n        int cur_max = v[0], overall_max = v[0];\n        vector<int> f(n);\n        vector<int> b(n);\n        f[0] = v[0];\n        \n        for(int i = 1; i < n; i++)\n        {\n            cur_max = max(v[i], cur_max + v[i]); \n            overall_max = max(overall_max, cur_max); \n  \n            f[i] = cur_max; \n        }\n        \n        cur_max = overall_max = b[n - 1] = v[n - 1];\n        for(int i = n - 2; i >= 0; i--)\n        {\n            cur_max = max(v[i], cur_max + v[i]); \n            overall_max = max(overall_max, cur_max); \n\n            b[i] = cur_max; \n        }\n        \n        res = overall_max;\n        for(int i = 1; i < n - 1; i++)\n        {\n            res = max(res, f[i - 1] + b[i + 1]);\n        }\n        return res;\n    }\n};\n```
[]