Maximum subarray sum possible after removing at most K array elements | Python3 program to implement the above approach ; Function to find the maximum subarray sum greater than or equal to 0 by removing K array elements ; Base case ; If overlapping subproblems already occurred ; Include current element in the subarray ; If K elements already removed from the subarray ; Remove current element from the subarray ; Utility function to find the maximum subarray sum by removing at most K array elements ; Stores maximum subarray sum by removing at most K elements ; Calculate maximum element in dp [ ] [ ] ; Update res ; If all array elements are negative ; Update res ; Driver Code
M = 100 NEW_LINE def mxSubSum ( i , arr , j ) : NEW_LINE INDENT global dp NEW_LINE if ( i == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = max ( 0 , arr [ i ] ) NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] NEW_LINE DEDENT X = max ( 0 , arr [ i ] + mxSubSum ( i - 1 , arr , j ) ) NEW_LINE if ( j == 0 ) : NEW_LINE INDENT dp [ i ] [ j ] = X NEW_LINE return X NEW_LINE DEDENT Y = mxSubSum ( i - 1 , arr , j - 1 ) NEW_LINE dp [ i ] [ j ] = max ( X , Y ) NEW_LINE return dp [ i ] [ j ] NEW_LINE DEDENT def MaximumSubarraySum ( n , arr , k ) : NEW_LINE INDENT mxSubSum ( n - 1 , arr , k ) NEW_LINE res = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( k + 1 ) : NEW_LINE INDENT res = max ( res , dp [ i ] [ j ] ) NEW_LINE DEDENT DEDENT if ( max ( arr ) < 0 ) : NEW_LINE INDENT res = max ( arr ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT dp = [ [ - 1 for i in range ( 100 ) ] for i in range ( 100 ) ] NEW_LINE arr = [ - 2 , 1 , 3 , - 2 , 4 , - 7 , 20 ] NEW_LINE K = 1 NEW_LINE N = len ( arr ) NEW_LINE print ( MaximumSubarraySum ( N , arr , K ) ) NEW_LINE DEDENT