[C++] Linear Scan, O(n) Space, 2*Modified Kadane
In the dp array, you will be storing values if you perform no deletion at index i.\nIn del array, you will store the maximum value if you perform a deletion at 
In the `dp` array, you will be storing values if you perform no deletion at index `i`.\nIn `del` array, you will store the maximum value if you perform a deletion at a particular index.\n\nTime Complexity : `O(n)`\nSpace Complexity: `O(n)`\n\n```\n\n\tdel[i] = max({\n\t\t\t\tdel[i-1] + arr[i-1], // continuing the subarray\n\t\t\t\tdp[i-1], // deleting the current element\n\t\t\t\tarr[i-1] }) // starting the subarray from the current element\n```\n\n```\nint maximumSum(vector<int>& arr) {\n        int n=arr.size();\n        bool hasg=false;\n        int mx = INT_MIN;\n        for(auto &i: arr) {\n            mx = max(mx, i);\n            if (i>=0) hasg = true; \n        }\n        if (!hasg) {\n            return mx; // if only negative elements are there\n        }\n        vector<int> dp(n+1, 0), del(n+1, 0);\n        mx = INT_MIN;\n        for(int i=1; i<=n; i++) {\n            dp[i] = max(dp[i-1] + arr[i-1], arr[i-1]);\n            del[i] = max({del[i-1] + arr[i-1], dp[i-1], arr[i-1]});\n            mx = max(mx, del[i]);\n        }\n        return mx;\n    }\n```
['Dynamic Programming', 'C']