Simple DP | Kadanes Algorithm | With Explanation 👍
Intuition\nThe problem description says "maximum subarray sum", hence we can think of some solution that revolves around kadanes algorithm.\n\n# Approach\nThere
# Intuition\nThe problem description says "maximum subarray sum", hence we can think of some solution that revolves around kadanes algorithm.\n\n# Approach\nThere are two main cases in this problem, we either don\'t delete an element or we delete an element.\n\n##### Case 1: Don\'t delete any element\nIn this case, we can directly use kadanes algorithm and find the maximum sum subarray.\n\n##### Case 2: Delete an element\n\nIn this case, we have to find the maximum subarray sum after deleting some element. But the question is, which element do we delete? One possible strategy is deleting the smallest element. Now, if all the elements in the array are positive and if we delete the smallest element, then the answer that  we get in case 1 will be greater than the answer that we get in case 2, hence the final answer won\'t be affected anyway as the final result will be the maximum of case 1 and case 2. But, if the array contains negative elements, then after removing the smallest negative element, there is a chance that we can find a subarray sum greater than that of case 1. Hence this seems like a good idea right? But it won\'t work for all the cases! Take the array `[1,-4,-5,-2,5,0,-1,2]` for example. If we delete -5 and run kadanes algorithm, the maximum subarray sum that we can get will be 6. But if we instead delete -1, the maximum subarray sum that we get is 7! The reason why this strategy doesn\'t work is because **the position of an element matters!** Hence deleting the smallest element is clearly not a good strategy. We can try to come up with many other heuristics for choosing the element to delete but most of them would fail....\n\nHence the best thing that we can do is to try deleting each element and take the maximum answer that we can get. How can we do that in O(n) time? We can run kadanes algorithm twice. Once from the left side and another from the right side. We have to maintain two arrays `left` and `right`. `left[i]` is the maximum of the subarray sums of all the subarrays ending at `arr[i]`. Similarily, `right[i]` is the maximum of the subarray sums of all the subarrays starting at `arr[i]`. After we find `left` and `right`, `left[i] + right[i+2]` will give us the maximum subarray sum after removing the element `arr[i]`. Hence we can use a for loop and iterate for all possible values of `i` and find the answer. The final answer will be the maximum of the answers that we get in case 1 and case 2. \n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        vector<int> left(arr.size());\n        vector<int> right(arr.size());\n        int sum=0, result=INT_MIN;\n\n        for(int i=0; i<arr.size(); i++) {\n            sum = max(sum+arr[i], arr[i]);\n            result = max(result, sum);\n            left[i] = sum;\n        }\n\n        sum = 0;\n\n        for(int i=arr.size()-1; i>=0; i--) {\n            sum = max(sum+arr[i], arr[i]);\n            right[i] = sum;\n        }\n\n        for(int i=0; i+2<arr.size(); i++) {\n            result = max(result, left[i]+right[i+2]);\n        }\n\n        return result;\n    }\n};\n```\n\n##### More Compact Version\n```cpp\nclass Solution {\npublic:\n    int maximumSum(vector<int>& arr) {\n        int result=INT_MIN, sum=0;\n        vector<int> dp(arr.size());\n\n        for(int i=0; i<arr.size(); i++) {\n            sum = max(sum+arr[i], arr[i]);\n            result = max(result, sum);\n            dp[i] = sum;\n        }\n\n        sum = 0;\n        \n        for(int i=arr.size()-1; i-2>=0; i--) {\n            sum = max(sum+arr[i], arr[i]);\n            result = max(result, dp[i-2]+sum);\n        }\n\n        return result;\n    }\n};\n```
['Dynamic Programming', 'C++']