Maximum subarray sum possible after removing at most K array elements | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define M  100 NEW_LINE int mxSubSum ( int i , int * arr , int j , int dp [ ] [ M ] ) { if ( i == 0 ) { return dp [ i ] [ j ] = max ( 0 , arr [ i ] ) ; } if ( dp [ i ] [ j ] != -1 ) { return dp [ i ] [ j ] ; } int X = 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 ] = max ( X , Y ) ; } int MaximumSubarraySum ( int n , int * arr , int k ) { int dp [ M ] [ M ] ; memset ( dp , -1 , sizeof ( dp ) ) ; mxSubSum ( n - 1 , arr , k , dp ) ; int res = 0 ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j <= k ; j ++ ) { res = max ( res , dp [ i ] [ j ] ) ; } } if ( * max_element ( arr , arr + n ) < 0 ) { res = * max_element ( arr , arr + n ) ; } return res ; } int main ( ) { int arr [ ] = { -2 , 1 , 3 , -2 , 4 , -7 , 20 } ; int K = 1 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << MaximumSubarraySum ( N , arr , K ) << endl ; return 0 ; }