Maximum subarray sum possible after removing at most K array elements | Java 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 ; Initialize dp [ ] [ ] to - 1 ; 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
import java . util . * ; class GFG { static final int M = 100 ; static int mxSubSum ( int i , int [ ] arr , int j , int dp [ ] [ ] ) { if ( i == 0 ) { return dp [ i ] [ j ] = Math . max ( 0 , arr [ i ] ) ; } if ( dp [ i ] [ j ] != - 1 ) { return dp [ i ] [ j ] ; } int X = Math . max ( 0 , arr [ i ] + mxSubSum ( i - 1 , arr , j , dp ) ) ; if ( j == 0 ) { return dp [ i ] [ j ] = X ; } int Y = mxSubSum ( i - 1 , arr , j - 1 , dp ) ; return dp [ i ] [ j ] = Math . max ( X , Y ) ; } static int MaximumSubarraySum ( int n , int [ ] arr , int k ) { int [ ] [ ] dp = new int [ M ] [ M ] ; for ( int i = 0 ; i < M ; i ++ ) for ( int j = 0 ; j < M ; j ++ ) dp [ i ] [ j ] = - 1 ; mxSubSum ( n - 1 , arr , k , dp ) ; int res = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j <= k ; j ++ ) { res = Math . max ( res , dp [ i ] [ j ] ) ; } } if ( Arrays . stream ( arr ) . max ( ) . getAsInt ( ) < 0 ) { res = Arrays . stream ( arr ) . max ( ) . getAsInt ( ) ; } return res ; } public static void main ( String [ ] args ) { int arr [ ] = { - 2 , 1 , 3 , - 2 , 4 , - 7 , 20 } ; int K = 1 ; int N = arr . length ; System . out . print ( MaximumSubarraySum ( N , arr , K ) + "NEW_LINE"); } }