C++ || Complete Explanation || Kadane''s Extension || Using left right Array
*INTUITION :- \n## Stores the Max subarray sum from left to right , takes the currsum = max(arr[i] , currsum + arr[i]) . i.e at any time max_ending_here (currsu
# ****INTUITION :- \n## Stores the Max subarray sum from left to right , takes the currsum = max(arr[i] , currsum + arr[i]) . i.e at any time max_ending_here (currsum+arr[i]) becomes smaller than current value of arr[i] , so replace currsum with arr[i] . \n\n## We are finding bestmax every time to stores the max subarray sum similar to kadanes algo considering no deletions .\n\n## Now we are storing the kadanes sum from right to left in right array .\n\n## Finally we are checking for every (ith) index to remove , not considering ith element in subarray , by taking ans = max ( ans , left[i-1] + right[i+1] ) .i.e gives kadanes sum from the left array till index i-1  and gives kadanes sum from right array till index i+1 . Not taking index i in considerations .\n\n## Finally we will get our required sum .\n\n# ****IF U FIND THIS SOLUTION HELPFUL , PLEASE UPVOTE IT !!!\n```\nint maximumSum(vector<int>& arr) {\n        \n          int n=arr.size();\n        \n        // if all numbers are negative return maxone\n        int maxnum=arr[0];\n        \n        for(int i=1;i<n;i++)\n        {\n            maxnum=max(maxnum , arr[i]);\n        }\n        \n        if(maxnum<=0)\n        {\n            return maxnum;\n        }\n        \n          // Make the left array for the storing the kadanes sum \n        // Mkae the right array for storing the kadanes sum from right to left \n        \n        vector<int> left(n) , right(n);\n        \n        int bestmax=0 , currmax=0;\n        \n        for( int i=0;i<n;i++)\n        {\n        currmax= max(arr[i] , currmax + arr[i]); // if(currmax + arr[i] <0) take just arr[i]\n            bestmax = max(bestmax , currmax);\n            left[i]=currmax;\n        }\n        currmax=0;\n        for(int i=n-1;i>=0;i--)\n        {\n            currmax=max(arr[i], currmax + arr[i]); \n            bestmax=max(bestmax , currmax);\n            right[i]=currmax;\n        }\n        \n        int ans=bestmax;\n        \n        for(int i=1;i<n-1;i++)\n        {\n            ans = max(ans , left[i-1] + right[i+1]);\n        }\n        \n        return ans;\n        \n    }\n```
['Dynamic Programming', 'C', 'C++']