Kadane’s Algorithm: Maximum Subarray Sum after removing at most one element

Problem Statement:

You are given an array, you need to return the maximum sum of a non empty subarray by removing at most one element.

Example:

Input: arr[] = {1, 2, 3, 4, -5}

Output: 10

Explanation: After removing -5, total sum is 10

Solution Explanation:

From the question, we can remove one element from the sub array to make the total greater.

So we can remove one -ve element.

So for each step, there are 2 cases to consider.

1. No Deletion case: In this step, is a regular kadane algorithm. So here we either extend the sub array or restart the sub array.

2. One deletion case: In this step, Continue from the previous deleted subarray or delete the current element and take the best sum before it.

Track both and update the overall maximum.

Time Complexity: O(n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include<algorithm>

using namespace std;

int solution(vector<int>& nums) 
{
     int n = nums.size();
     int maxi = nums[0];
     int nd = nums[0]; // no deletion
     int od = INT_MIN;  // one deletion

     for(int i=1;i<n;i++)
     {
       
        od = max(nd, od==INT_MIN?INT_MIN:od+nums[i]);
        nd = max(nums[i],nums[i]+nd);

        maxi = max({maxi,od,nd});
     }


   return maxi;
}

int main()
{
    vector<int> arr =  {1, 2, 3, 4, -5 };
  
    cout << solution(arr);
    return 0;
}

Output

10