C++ Fast & Easy - Modified Kadane's Algorithm
INTUITION\nProblems related to largest contiguous sub-array sum should be visualised as a modified implementation of Kadane\'s algorithm.\n\n# APPROACH\nWe know
# INTUITION\nProblems related to largest contiguous sub-array sum should be visualised as a modified implementation of Kadane\'s algorithm.\n\n# APPROACH\nWe know that the largest contiguous sub-array sum can be easily computed using Kadane\'s Algorithm. Given problem is a modified version of it, with at most 1 deletion. So we will break the problem into three possible cases:\n\n**Case 1 : No deletion | Maximum contiguous sub-array sum**\nIf we do not consider any deletion whatsoever, we can use Kadane\'s Algorithm to compute our answer (till here).\n\n**Case 2 : No deletion | At least one element in sub-array**\nIt might be possible that Kadane\'s Algorithm gives answer as zero (if not even a single element is positive). In that case, we calculate the least negative element (or the max element in the array) to update our answer (till here).\n\n**Case 3 : One deletion | Checking by deleting a negative element**\nThis is the major case.\nFor any negative element at index \'i\' in the array, let:\nMax prefix sum (max contiguous sub-array sum ending at i-1) be p\nMax suffix sum (max contiguous sub-array sum beginning from i+1) be s\nThen after deleting the negative element, the sum we get would be (p+s).\nSo we can update our answer to be the maximum we get from all iterations and the two above cases.\n# CODE\n```\nclass Solution {\npublic:\n    int kadane(vector<int> a, int n) {\n        \n        int maxeh=0, maxtn=0;\n        for (int i=0; i<n; i++) {\n            maxeh=maxeh+a[i];\n            if (maxeh<0) maxeh=0;\n            maxtn=max(maxtn,maxeh);\n        }\n        return maxtn;\n    }\n    \n    int maxel (vector<int> a, int n) {\n        \n        if (n==1) return a[0];\n        int maxx=a[0];\n        for (int i=0; i<n; i++) {\n            if (a[i]>maxx) maxx=a[i]; \n        }\n        return maxx;\n    }\n    \n    int maximumSum(vector<int>& a) {\n        \n        int n=a.size();\n        \n        if (n==0) return 0;\n        if (n==1) return a[0];\n        \n        vector<int> maxehl(n,0);\n        maxehl[0]=max(a[0],0);\n        \n        for (int i=1; i<n; i++) {\n            maxehl[i]=maxehl[i-1]+a[i];\n            if (maxehl[i]<0) maxehl[i]=0;\n        }\n        \n        vector<int> maxehr(n,0);\n        maxehr[n-1]=max(a[n-1],0);\n        \n        for (int i=n-2; i>=0; i--) {\n            maxehr[i]=maxehr[i+1]+a[i];\n            if (maxehr[i]<0) maxehr[i]=0;\n        }\n        \n        // case 1 : sum of largest contiguous sub-array\n        // no deletion\n        int ans=kadane(a,n);\n        \n        // case 2 : least negative no. in case of all negative\n        // no deletion\n        if (ans==0) {\n            ans=maxel(a,n);\n        }\n        \n        // case 3 : deleting one negative element\n        // one deletion\n        for (int i=1; i<n-1; i++) {\n            if (a[i]<0) {\n                ans=max(ans, maxehl[i-1]+maxehr[i+1]  );\n            }\n        }\n        if (ans==0) return maxel(a,n);\n        return ans;\n    }\n};\n```
[]