Maximum subarray sum possible after removing at most K array elements | Javascript 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 overlapping subproblems of the recurrence relation ; 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
var M = 100 ; function mxSubSum ( i , arr , j , dp ) { if ( i == 0 ) { dp [ i ] [ j ] = Math . max ( 0 , arr [ i ] ) ; return dp [ i ] [ j ] ; } if ( dp [ i ] [ j ] != - 1 ) { return dp [ i ] [ j ] ; } var X = Math . max ( 0 , arr [ i ] + mxSubSum ( i - 1 , arr , j , dp ) ) ; if ( j == 0 ) { dp [ i ] [ j ] = X ; return dp [ i ] [ j ] } var Y = mxSubSum ( i - 1 , arr , j - 1 , dp ) ; dp [ i ] [ j ] = Math . max ( X , Y ) ; return dp [ i ] [ j ] } function MaximumSubarraySum ( n , arr , k ) { var dp = Array . from ( Array ( M ) , ( ) => Array ( M ) . fill ( - 1 ) ) ; mxSubSum ( n - 1 , arr , k , dp ) ; var res = 0 ; for ( var i = 0 ; i < n ; i ++ ) { for ( var j = 0 ; j <= k ; j ++ ) { res = Math . max ( res , dp [ i ] [ j ] ) ; } } if ( arr . reduce ( ( a , b ) => Math . max ( a , b ) ) < 0 ) { res = arr . reduce ( ( a , b ) => Math . max ( a , b ) ) ; } return res ; } var arr = [ - 2 , 1 , 3 , - 2 , 4 , - 7 , 20 ] ; var K = 1 ; var N = arr . length ; document . write ( MaximumSubarraySum ( N , arr , K ) ) ;