Maximum Subarray Sum after inverting at most two elements | Function to return the maximum required sub - array sum ; Creating one based indexing ; 2d array to contain solution for each step ; Case 1 : Choosing current or ( current + previous ) whichever is smaller ; Case 2 : ( a ) Altering sign and add to previous case 1 or value 0 ; Case 2 : ( b ) Adding current element with previous case 2 and updating the maximum ; Case 3 : ( a ) Altering sign and add to previous case 2 ; Case 3 : ( b ) Adding current element with previous case 3 ; Updating the maximum value of variable ans ; Return the final solution ; Driver code
def maxSum ( a , n ) : NEW_LINE INDENT ans = 0 NEW_LINE arr = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT arr [ i ] = a [ i - 1 ] NEW_LINE DEDENT dp = [ [ 0 for i in range ( 3 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 0 , n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = max ( arr [ i ] , dp [ i - 1 ] [ 0 ] + arr [ i ] ) NEW_LINE dp [ i ] [ 1 ] = max ( 0 , dp [ i - 1 ] [ 0 ] ) - arr [ i ] NEW_LINE if i >= 2 : NEW_LINE INDENT dp [ i ] [ 1 ] = max ( dp [ i ] [ 1 ] , dp [ i - 1 ] [ 1 ] + arr [ i ] ) NEW_LINE DEDENT if i >= 2 : NEW_LINE INDENT dp [ i ] [ 2 ] = dp [ i - 1 ] [ 1 ] - arr [ i ] NEW_LINE DEDENT if i >= 3 : NEW_LINE INDENT dp [ i ] [ 2 ] = max ( dp [ i ] [ 2 ] , dp [ i - 1 ] [ 2 ] + arr [ i ] ) NEW_LINE DEDENT ans = max ( ans , dp [ i ] [ 0 ] ) NEW_LINE ans = max ( ans , dp [ i ] [ 1 ] ) NEW_LINE ans = max ( ans , dp [ i ] [ 2 ] ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ - 5 , 3 , 2 , 7 , - 8 , 3 , 7 , - 9 , 10 , 12 , - 6 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maxSum ( arr , n ) ) NEW_LINE DEDENT