Maximum subarray sum possible after removing at most K array elements
Given an array arr[] of size N and an integer K, the task is to find the maximum subarray sum by removing at most K elements from the array.
Examples:
Input: arr[] = { -2, 1, 3, -2, 4, -7, 20 }, K = 1
Output: 26
Explanation:
Removing arr[5] from the array modifies arr[] to { -2, 1, 3, -2, 4, 20 }
Subarray with maximum sum is { 1, 3, -2, 4, 20 }.
Therefore, the required output is 26.Input:arr[] = { -1, 1, -1, -1, 1, 1 }, K=2
Output: 3
Explanation:
Removing arr[2] and arr[3] from the array modifies arr[] to { – 1, 1, 1, 1}
Subarray with maximum sum is { 1, 1, 1 }.
Therefore, the required output is 3.
Approach: The problem can be solved using Dynamic Programming. The idea is to use the concept of Kadane’s algorithm. Follow the steps below to solve the problem:
- Traverse the array arr[] and for every array element following two operations needs to be performed:
- Remove the current array element from the subarray.
- Include the current array element in the subarray.
- Therefore, the recurrence relation to solve this problem is as follows:
mxSubSum(i, j) = max(max(0, arr[i] + mxSubSum(i – 1, j)), mxSubSum(i – 1, j – 1))
i: Stores index of array element
j: Maximum count of elements that can be removed from the subarray
mxSubSum(i, j): Return maximum subarray sum from the subarray { arr[i], arr[N – 1] } by removing K – j array elements.
- Initialize a 2D array, say dp[][], to store the overlapping subproblems of the above recurrence relation.
- Fill the dp[][] array using memoization.
- Find the maximum element from the dp[][] array say, res.
- Initialize a variable, say Max, to store the largest element present in the array arr[].
- If all the array elements are negative, then update res = max(res, Max).
- Finally, print res as the required answer.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define M 100// Function to find the maximum subarray// sum greater than or equal to 0 by// removing K array elementsint mxSubSum(int i, int* arr, int j, int dp[][M]){ // Base case if (i == 0) { return dp[i][j] = max(0, arr[i]); } // If overlapping subproblems // already occurred if (dp[i][j] != -1) { return dp[i][j]; } // Include current element in the subarray int X = max(0, arr[i] + mxSubSum(i - 1, arr, j, dp)); // If K elements already removed // from the subarray if (j == 0) { return dp[i][j] = X; } // Remove current element from the subarray int Y = mxSubSum(i - 1, arr, j - 1, dp); return dp[i][j] = max(X, Y);}// Utility function to find the maximum subarray// sum by removing at most K array elementsint MaximumSubarraySum(int n, int* arr, int k){ // Stores overlapping subproblems // of the recurrence relation int dp[M][M]; // Initialize dp[][] to -1 memset(dp, -1, sizeof(dp)); mxSubSum(n - 1, arr, k, dp); // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[][] for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { // Update res res = max(res, dp[i][j]); } } // If all array elements are negative if (*max_element(arr, arr + n) < 0) { // Update res res = *max_element(arr, arr + n); } return res;}// Driver Codeint 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;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{static final int M = 100;// Function to find the maximum subarray// sum greater than or equal to 0 by// removing K array elementsstatic int mxSubSum(int i, int []arr, int j, int dp[][]){ // Base case if (i == 0) { return dp[i][j] = Math.max(0, arr[i]); } // If overlapping subproblems // already occurred if (dp[i][j] != -1) { return dp[i][j]; } // Include current element in the subarray int X = Math.max(0, arr[i] + mxSubSum(i - 1, arr, j, dp)); // If K elements already removed // from the subarray if (j == 0) { return dp[i][j] = X; } // Remove current element from the subarray int Y = mxSubSum(i - 1, arr, j - 1, dp); return dp[i][j] = Math.max(X, Y);}// Utility function to find the maximum subarray// sum by removing at most K array elementsstatic int MaximumSubarraySum(int n, int []arr, int k){ // Stores overlapping subproblems // of the recurrence relation int [][]dp = new int[M][M]; // Initialize dp[][] to -1 for (int i = 0; i < M; i++) for (int j = 0; j < M; j++) dp[i][j] = -1; mxSubSum(n - 1, arr, k, dp); // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[][] for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { // Update res res = Math.max(res, dp[i][j]); } } // If all array elements are negative if (Arrays.stream(arr).max().getAsInt() < 0) { // Update res res = Arrays.stream(arr).max().getAsInt(); } return res;}// Driver Codepublic 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) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachM = 100# Function to find the maximum subarray# sum greater than or equal to 0 by# removing K array elementsdef mxSubSum(i, arr, j): global dp # Base case if (i == 0): dp[i][j] = max(0, arr[i]) return dp[i][j] # If overlapping subproblems # already occurred if (dp[i][j] != -1): return dp[i][j] # Include current element in the subarray X = max(0, arr[i] + mxSubSum(i - 1, arr, j)) # If K elements already removed # from the subarray if (j == 0): dp[i][j] = X return X # Remove current element from the subarray Y = mxSubSum(i - 1, arr, j - 1) dp[i][j] = max(X, Y) return dp[i][j]# Utility function to find the maximum subarray# sum by removing at most K array elements# Utility function to find the maximum subarray# sum by removing at most K array elementsdef MaximumSubarraySum(n, arr, k): mxSubSum(n - 1, arr, k) # Stores maximum subarray sum by # removing at most K elements res = 0 # Calculate maximum element # in dp[][] for i in range(n): for j in range(k + 1): # Update res res = max(res, dp[i][j]) # If all array elements are negative if (max(arr) < 0): # Update res res = max(arr) return res# Driver Codeif __name__ == '__main__': dp = [[-1 for i in range(100)] for i in range(100)] arr = [-2, 1, 3, -2, 4, -7, 20] K = 1 N = len(arr) print(MaximumSubarraySum(N, arr, K))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections;class GFG{ static int M = 100;// Function to find the maximum subarray// sum greater than or equal to 0 by// removing K array elementsstatic int mxSubSum(int i, int []arr, int j, int [,]dp){ // Base case if (i == 0) { return dp[i, j] = Math.Max(0, arr[i]); } // If overlapping subproblems // already occurred if (dp[i, j] != -1) { return dp[i, j]; } // Include current element in the subarray int X = Math.Max(0, arr[i] + mxSubSum(i - 1, arr, j, dp)); // If K elements already removed // from the subarray if (j == 0) { return dp[i, j] = X; } // Remove current element from the subarray int Y = mxSubSum(i - 1, arr, j - 1, dp); return dp[i, j] = Math.Max(X, Y);}// Utility function to find the maximum subarray// sum by removing at most K array elementsstatic int MaximumSubarraySum(int n, int []arr, int k){ // Stores overlapping subproblems // of the recurrence relation int [,]dp = new int[M, M]; // Initialize dp[,] to -1 for(int i = 0; i < M; i++) for(int j = 0; j < M; j++) dp[i, j] = -1; mxSubSum(n - 1, arr, k, dp); // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[,] for(int i = 0; i < n; i++) { for(int j = 0; j <= k; j++) { // Update res res = Math.Max(res, dp[i, j]); } } Array.Sort(arr); // If all array elements are negative if (arr[n - 1] < 0) { // Update res res = arr[n - 1]; } return res;}// Driver Codepublic static void Main(String[] args){ int []arr = { -2, 1, 3, -2, 4, -7, 20 }; int K = 1; int N = arr.Length; Console.WriteLine(MaximumSubarraySum(N, arr, K));}}// This code is contributed by AnkThon |
Javascript
<script>// Javascript program to implement// the above approachvar M = 100;// Function to find the maximum subarray// sum greater than or equal to 0 by// removing K array elementsfunction mxSubSum(i, arr, j, dp){ // Base case if (i == 0) { dp[i][j] = Math.max(0, arr[i]); return dp[i][j]; } // If overlapping subproblems // already occurred if (dp[i][j] != -1) { return dp[i][j]; } // Include current element in the subarray var X = Math.max( 0, arr[i] + mxSubSum(i - 1, arr, j, dp)); // If K elements already removed // from the subarray if (j == 0) { dp[i][j] = X; return dp[i][j] } // Remove current element from the subarray var Y = mxSubSum(i - 1, arr, j - 1, dp); dp[i][j] = Math.max(X, Y); return dp[i][j]}// Utility function to find the maximum subarray// sum by removing at most K array elementsfunction MaximumSubarraySum(n, arr, k){ // Stores overlapping subproblems // of the recurrence relation var dp = Array.from(Array(M), () => Array(M).fill(-1)); mxSubSum(n - 1, arr, k, dp); // Stores maximum subarray sum by // removing at most K elements var res = 0; // Calculate maximum element // in dp[][] for(var i = 0; i < n; i++) { for(var j = 0; j <= k; j++) { // Update res res = Math.max(res, dp[i][j]); } } // If all array elements are negative if (arr.reduce((a, b) => Math.max(a, b)) < 0) { // Update res res = arr.reduce((a, b) => Math.max(a, b)); } return res;}// Driver Codevar arr = [ -2, 1, 3, -2, 4, -7, 20 ];var K = 1;var N = arr.length;document.write( MaximumSubarraySum(N, arr, K));// This code is contributed by rrrtnx</script> |
Output:
26
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memorization(top-down) because memorization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a vector to store the solution of the subproblems.
- Initialize the table with base cases
- Fill up the table iteratively
- Return the final solution
Implementation :
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;#define M 100// Utility function to find the maximum subarray// sum by removing at most K array elementsint MaximumSubarraySum(int n, int* arr, int k){ // dp[i][j]: Stores maximum subarray sum // by removing at most j elements from // subarray ending at i-th index int dp[n][k + 1]; // Initialize dp[][] to 0 memset(dp, 0, sizeof(dp)); // Initialization for i = 0 dp[0][0] = max(0, arr[0]); // Calculate maximum subarray sum by // removing at most j elements for // subarrays ending at i-th index for (int i = 1; i < n; i++) { for (int j = 0; j <= k; j++) { // Include current element in the subarray int X = max(0, arr[i] + dp[i - 1][j]); // Remove current element from the subarray int Y = (j > 0) ? dp[i - 1][j - 1] : 0; dp[i][j] = max(X, Y); } } // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[][] for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { // Update res res = max(res, dp[i][j]); } } // If all array elements are negative if (*max_element(arr, arr + n) < 0) { // Update res res = *max_element(arr, arr + n); } return res;}// Driver Codeint 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;}// this code is contributed by bhardwajji |
Java
import java.util.Arrays;class Main { // Utility function to find the maximum subarray // sum by removing at most K array elements static int maximumSubarraySum(int n, int[] arr, int k) { // dp[i][j]: Stores maximum subarray sum // by removing at most j elements from // subarray ending at i-th index int[][] dp = new int[n][k + 1]; // Initialize dp[][] to 0 for (int i = 0; i < n; i++) { Arrays.fill(dp[i], 0); } // Initialization for i = 0 dp[0][0] = Math.max(0, arr[0]); // Calculate maximum subarray sum by // removing at most j elements for // subarrays ending at i-th index for (int i = 1; i < n; i++) { for (int j = 0; j <= k; j++) { // Include current element in the subarray int X = Math.max(0, arr[i] + dp[i - 1][j]); // Remove current element from the subarray int Y = (j > 0) ? dp[i - 1][j - 1] : 0; dp[i][j] = Math.max(X, Y); } } // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[][] for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { // Update res res = Math.max(res, dp[i][j]); } } // If all array elements are negative if (Arrays.stream(arr).max().getAsInt() < 0) { // Update res res = Arrays.stream(arr).max().getAsInt(); } return res; } // Driver Code public static void main(String[] args) { int[] arr = { -2, 1, 3, -2, 4, -7, 20 }; int K = 1; int N = arr.length; System.out.println(maximumSubarraySum(N, arr, K)); }} |
Python
# Python program to implement# the above approach# Utility function to find the maximum subarray# sum by removing at most K array elementsdef MaximumSubarraySum(n, arr, k): # dp[i][j]: Stores maximum subarray sum # by removing at most j elements from # subarray ending at i-th index dp = [[0 for j in range(k+1)] for i in range(n)] # Initialization for i = 0 dp[0][0] = max(0, arr[0]) # Calculate maximum subarray sum by # removing at most j elements for # subarrays ending at i-th index for i in range(1, n): for j in range(k+1): # Include current element in the subarray X = max(0, arr[i] + dp[i - 1][j]) # Remove current element from the subarray Y = dp[i - 1][j - 1] if j > 0 else 0 dp[i][j] = max(X, Y) # Stores maximum subarray sum by # removing at most K elements res = 0 # Calculate maximum element in dp[][] for i in range(n): for j in range(k+1): # Update res res = max(res, dp[i][j]) # If all array elements are negative if max(arr) < 0: # Update res res = max(arr) return res# Driver Codeif __name__ == '__main__': arr = [-2, 1, 3, -2, 4, -7, 20] K = 1 N = len(arr) print(MaximumSubarraySum(N, arr, K)) |
C#
using System;using System.Linq;class MainClass { // Utility function to find the maximum subarray // sum by removing at most K array elements static int maximumSubarraySum(int n, int[] arr, int k) { // dp[i][j]: Stores maximum subarray sum // by removing at most j elements from // subarray ending at i-th index int[][] dp = new int[n][]; // Initialize dp[][] to 0 for (int i = 0; i < n; i++) { dp[i] = new int[k + 1]; for (int j = 0; j <= k; j++) { dp[i][j] = 0; } } // Initialization for i = 0 dp[0][0] = Math.Max(0, arr[0]); // Calculate maximum subarray sum by // removing at most j elements for // subarrays ending at i-th index for (int i = 1; i < n; i++) { for (int j = 0; j <= k; j++) { // Include current element in the subarray int X = Math.Max(0, arr[i] + dp[i - 1][j]); // Remove current element from the subarray int Y = (j > 0) ? dp[i - 1][j - 1] : 0; dp[i][j] = Math.Max(X, Y); } } // Stores maximum subarray sum by // removing at most K elements int res = 0; // Calculate maximum element // in dp[][] for (int i = 0; i < n; i++) { for (int j = 0; j <= k; j++) { // Update res res = Math.Max(res, dp[i][j]); } } // If all array elements are negative if (arr.Max() < 0) { // Update res res = arr.Max(); } return res; } // Driver Code public static void Main() { int[] arr = { -2, 1, 3, -2, 4, -7, 20 }; int K = 1; int N = arr.Length; Console.WriteLine(maximumSubarraySum(N, arr, K)); }} |
Javascript
// JavaScript program to implement// the above approach// Utility function to find the maximum subarray// sum by removing at most K array elementsfunction MaximumSubarraySum(n, arr, k) { // dp[i][j]: Stores maximum subarray sum // by removing at most j elements from // subarray ending at i-th index let dp = new Array(n); for (let i = 0; i < n; i++) { dp[i] = new Array(k + 1).fill(0); } // Initialization for i = 0 dp[0][0] = Math.max(0, arr[0]); // Calculate maximum subarray sum by // removing at most j elements for // subarrays ending at i-th index for (let i = 1; i < n; i++) { for (let j = 0; j <= k; j++) { // Include current element in the subarray let X = Math.max(0, arr[i] + dp[i - 1][j]); // Remove current element from the subarray let Y = (j > 0) ? dp[i - 1][j - 1] : 0; dp[i][j] = Math.max(X, Y); } } // Stores maximum subarray sum by // removing at most K elements let res = 0; // Calculate maximum element // in dp[][] for (let i = 0; i < n; i++) { for (let j = 0; j <= k; j++) { // Update res res = Math.max(res, dp[i][j]); } } // If all array elements are negative if (Math.max(...arr) < 0) { // Update res res = Math.max(...arr); } return res;}// Driver Codelet arr = [-2, 1, 3, -2, 4, -7, 20];let K = 1;let N = arr.length;console.log(MaximumSubarraySum(N, arr, K));// This code is contributed by Prajwal Kandekar |
Output:
26
Time Complexity: O(N * K)
Auxiliary Space: O(N * K)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
