C++ one traversal with O(1) space and O(n) time
Extension of Kadane\'s Algorithm\n\nThe idea is to keep track of max sum subarray ending at each index of array, without deleting that element and with deleting
**Extension of Kadane\'s Algorithm**\n\nThe idea is to keep track of max sum subarray ending at each index of array, without deleting that element and with deleting that element.\n**prevNotDeleted = max(prevNotDeleted + a[i], a[i])**\nand \n**prevDeleted = max(prevNotDeleted, prevDeleted+a[i])**\nwe will keep updating these values at each index and our answer will be the maximum of these two in entire array.\n```\nint maximumSum(vector<int>& a) {\n        int prevNotDeleted = a[0];\n        int prevDeleted = 0;\n        int maxi = a[0];\n        int n = a.size();\n        for(int i=1; i<n; i++)\n        {\n            prevDeleted = max(prevNotDeleted, prevDeleted+a[i]);\n            prevNotDeleted = max(prevNotDeleted+a[i], a[i]);\n            maxi = max(maxi, max(prevNotDeleted, prevDeleted));\n        }\n        return maxi;\n    }\n```\n\nPlease upvote if you like the solution
['C']