Dada una array arr[] de tamaño N y un número entero K , la tarea es encontrar la suma máxima de subarreglo eliminando como máximo K elementos de la array.
Ejemplos:
Entrada: arr[] = { -2, 1, 3, -2, 4, -7, 20 }, K = 1
Salida: 26
Explicación:
Eliminar arr[5] de la array modifica arr[] a { -2, 1, 3, -2, 4, 20 }
El subarreglo con suma máxima es { 1, 3, -2, 4, 20 }.
Por lo tanto, la salida requerida es 26.Entrada: arr[] = { -1, 1, -1, -1, 1, 1 }, K=2
Salida: 3
Explicación:
Eliminar arr[2] y arr[3] de la array modifica arr[] a { – 1, 1, 1, 1}
El subarreglo con suma máxima es { 1, 1, 1 }.
Por lo tanto, la salida requerida es 3.
Planteamiento: El problema se puede resolver usando Programación Dinámica . La idea es utilizar el concepto del algoritmo de Kadane . Siga los pasos a continuación para resolver el problema:
- Atraviese la array arr[] y para cada elemento de la array se deben realizar las siguientes dos operaciones:
- Elimina el elemento de array actual del subarreglo.
- Incluya el elemento de array actual en el subarreglo.
- Por lo tanto, la relación de recurrencia para resolver este problema es la siguiente:
mxSubSum(i, j) = max(max(0, arr[i] + mxSubSum(i – 1, j)), mxSubSum(i – 1, j – 1))
i: Almacena el índice del elemento de array
j: Cantidad máxima de elementos que se pueden eliminar del
subarreglo mxSubSum(i, j): Devuelve la suma máxima del subarreglo del subarreglo {arr[i], arr[N – 1] } al eliminar K – j elementos de array.
- Inicialice una array 2D , digamos dp[][] , para almacenar los subproblemas superpuestos de la relación de recurrencia anterior.
- Llene la array dp[][] usando memoization .
- Encuentre el elemento máximo de la array dp[][] , por ejemplo, res .
- Inicialice una variable, digamos Max , para almacenar el elemento más grande presente en la array arr[] .
- Si todos los elementos de la array son negativos, actualice res = max(res, Max) .
- Finalmente, imprima res como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
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 elements
int 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 elements
int 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 Code
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;
}
Java
// Java program to implement
// the above approach
import 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 elements
static 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 elements
static 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 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.print(MaximumSubarraySum(N, arr, K) +"\n");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach M = 100 # Function to find the maximum subarray # sum greater than or equal to 0 by # removing K array elements def 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 elements def 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 Code if __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 approach
using 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 elements
static 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 elements
static 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 Code
public 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 approach
var M = 100;
// Function to find the maximum subarray
// sum greater than or equal to 0 by
// removing K array elements
function 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 elements
function 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 Code
var 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>
Producción:
26
Complejidad temporal: O(N * K)
Espacio auxiliar: O(N * K)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA