Maximize the maximum subarray sum after removing atmost one element | C ++ implementation of the approach ; Function to return the maximum sub - array sum ; Initialized ; Traverse in the array ; Increase the sum ; If sub - array sum is more than the previous ; If sum is negative ; Function that returns the maximum sub - array sum after removing an element from the same sub - array ; Maximum sub - array sum using Kadane 's Algorithm ; Re - apply Kadane 's with minor changes ; Increase the sum ; If sub - array sum is greater than the previous ; If elements are 0 , no removal ; If elements are more , then store the minimum value in the sub - array obtained till now ; If sum is negative ; Re - initialize everything ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSubArraySum ( int a [ ] , int size ) { int max_so_far = INT_MIN , max_ending_here = 0 ; for ( int i = 0 ; i < size ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; if ( max_so_far < max_ending_here ) max_so_far = max_ending_here ; if ( max_ending_here < 0 ) max_ending_here = 0 ; } return max_so_far ; } int maximizeSum ( int a [ ] , int n ) { int cnt = 0 ; int mini = INT_MAX ; int minSubarray = INT_MAX ; int sum = maxSubArraySum ( a , n ) ; int max_so_far = INT_MIN , max_ending_here = 0 ; for ( int i = 0 ; i < n ; i ++ ) { max_ending_here = max_ending_here + a [ i ] ; cnt ++ ; minSubarray = min ( a [ i ] , minSubarray ) ; if ( sum == max_ending_here ) { if ( cnt == 1 ) mini = min ( mini , 0 ) ; else mini = min ( mini , minSubarray ) ; } if ( max_ending_here < 0 ) { max_ending_here = 0 ; cnt = 0 ; minSubarray = INT_MAX ; } } return sum - mini ; } int main ( ) { int a [ ] = { 1 , 2 , 3 , -2 , 3 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; cout << maximizeSum ( a , n ) ; return 0 ; }