Maximize the maximum subarray sum after removing atmost one element | Python3 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
import sys ; NEW_LINE def maxSubArraySum ( a , size ) : NEW_LINE INDENT max_so_far = - ( sys . maxsize - 1 ) ; NEW_LINE max_ending_here = 0 ; NEW_LINE for i in range ( size ) : NEW_LINE INDENT max_ending_here = max_ending_here + a [ i ] ; NEW_LINE if ( max_so_far < max_ending_here ) : NEW_LINE INDENT max_so_far = max_ending_here ; NEW_LINE DEDENT if ( max_ending_here < 0 ) : NEW_LINE INDENT max_ending_here = 0 ; NEW_LINE DEDENT DEDENT return max_so_far ; NEW_LINE DEDENT def maximizeSum ( a , n ) : NEW_LINE INDENT cnt = 0 ; NEW_LINE mini = sys . maxsize ; NEW_LINE minSubarray = sys . maxsize ; NEW_LINE sum = maxSubArraySum ( a , n ) ; NEW_LINE max_so_far = - ( sys . maxsize - 1 ) ; NEW_LINE max_ending_here = 0 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT max_ending_here = max_ending_here + a [ i ] ; NEW_LINE cnt += 1 ; NEW_LINE minSubarray = min ( a [ i ] , minSubarray ) ; NEW_LINE if ( sum == max_ending_here ) : NEW_LINE INDENT if ( cnt == 1 ) : NEW_LINE INDENT mini = min ( mini , 0 ) ; NEW_LINE DEDENT else : NEW_LINE INDENT mini = min ( mini , minSubarray ) ; NEW_LINE DEDENT DEDENT if ( max_ending_here < 0 ) : NEW_LINE INDENT max_ending_here = 0 ; NEW_LINE cnt = 0 ; NEW_LINE minSubarray = sys . maxsize ; NEW_LINE DEDENT DEDENT return sum - mini ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 1 , 2 , 3 , - 2 , 3 ] ; NEW_LINE n = len ( a ) NEW_LINE print ( maximizeSum ( a , n ) ) ; NEW_LINE DEDENT