C++ || 2-sided Kadane's Algorithm || O(n) Time || O(n) space
class Solution {\npublic:\n    int maximumSum(vector& a) {\n        \n        int i,j,n=a.size();\n        if(!n) return 0;\n        \n        for(i=0;i0)\n    
class Solution {\npublic:\n    int maximumSum(vector<int>& a) {\n        \n        int i,j,n=a.size();\n        if(!n) return 0;\n        \n        for(i=0;i<n;i++)\n            if(a[i]>0)\n                break;\n\n        if(i==n)\n        {\n            j=a[0];\n            for(i=0;i<n;i++)\n                j = max(j, a[i]);\n            return j;\n        }\n            \n        vector<int>left(n,0);\n        vector<int>right(n,0);\n        \n        int sumLeft = a[0];\n        if(a[0]<0)\n            sumLeft = 0;\n        \n        for(i=1;i<n;i++)\n        {\n            left[i] = sumLeft;\n            sumLeft += a[i];\n            sumLeft = max(sumLeft, 0);\n        }\n        \n        int sumRight = a[n-1];\n        if(a[n-1]<0)\n            sumRight = 0;\n        \n        for(i=n-2;i>=0;i--)\n        {\n            right[i] = sumRight;\n            sumRight += a[i];\n            sumRight = max(sumRight, 0);\n        }\n        \n        int ans=INT_MIN;\n        for(i=0;i<n;i++)\n        {\n            if(a[i]>0)\n                ans = max(a[i]+left[i]+right[i], ans);\n            else\n                ans = max(left[i]+right[i], ans);\n        }    \n        return ans;\n    }\n};
['Dynamic Programming']