Dada una array 2D Blocks[][] que consta de N filas de longitud variable. La tarea es seleccionar como máximo M elementos con la suma máxima posible de Blocks[][] desde el inicio o el final de una fila.
Ejemplos:
Entrada: N = 3, M = 4
Bloques[][] = {{2, 3, 5}, {-1, 7}, {8, 10}}
Salida: 30
Explicación:
Seleccione {5} de la primera fila .
Seleccione {7} de la 2ª fila.
Seleccione {8, 10} de la 3ª fila.Entrada: N = 3, M = 2
Bloques[][] = {{100, 3, -1}, {-1, 7, 10}, {8, 10, 15}}
Salida: 115
Explicación:
seleccione {100 } desde la 1ª fila.
Saltar 2ª fila.
Seleccione {15} de la 3ª fila.
Enfoque ingenuo: el enfoque más simple es iterar a través de todas las filas de la array e insertar todos los elementos en un vector y ordenarlo . Calcula la suma de los últimos M elementos e imprímela como la respuesta requerida.
Complejidad temporal: O(N * KlogK), donde K es el tamaño máximo que puede tener cualquier bloque.
Espacio Auxiliar: O(N * K)
Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es usar Programación Dinámica usando Memoización . Siga los pasos a continuación:
- Dadas N filas y de cada fila, seleccione cualquier segmento de la i -ésima fila, digamos de l a r .
- El conteo de elementos en la i -ésima fila es (r – l + 1) y continúe con la siguiente fila.
- Para calcular la suma máxima, utilicela técnica de suma de prefijos para calcular la suma.
- Inicialice una array 2D dp[][] , donde dp[N][M] almacena la suma máxima seleccionando como máximo M elementos de N filas.
- Considere los siguientes dos escenarios:
- O salta la fila actual.
- Seleccione cualquier segmento de la fila actual que no exceda el número de elementos seleccionados.
- Considere los siguientes dos escenarios:
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to select m elements
// having maximum sum
long mElementsWithMaxSum(vector<vector<int> > matrix,
int M, int block,
vector<vector<int> > dp)
{
// Base case
if (block == matrix.size())
return 0;
// If precomputed subproblem occurred
if (dp[block][M] != -1)
return dp[block][M];
// Either skip the current row
long ans = mElementsWithMaxSum(matrix, M,
block + 1, dp);
// Iterate through all the possible
// segments of current row
for(int i = 0;
i < matrix[block].size(); i++)
{
for(int j = i;
j < matrix[block].size(); j++)
{
// Check if it is possible to select
// elements from i to j
if (j - i + 1 <= M)
{
// Compute the sum of i to j as
// calculated
ans = max(ans, matrix[block][j] -
((i - 1) >= 0 ?
matrix[block][i - 1] : 0) +
mElementsWithMaxSum(matrix,
M - j +
i - 1,
block + 1, dp));
}
}
}
// Store the computed answer and return
return dp[block][M] = ans;
}
// Function to precompute the prefix sum
// for every row of the matrix
void preComputing(vector<vector<int>> matrix,
int N)
{
// Preprocessing to calculate sum from i to j
for(int i = 0; i < N; i++)
{
for(int j = 0; j < matrix[i].size(); j++)
{
matrix[i][j] = (j > 0 ?
matrix[i][j - 1] : 0) +
matrix[i][j];
}
}
}
// Utility function to select m elements having
// maximum sum
void mElementsWithMaxSumUtil(vector<vector<int>> matrix,
int M, int N)
{
// Preprocessing step
preComputing(matrix, N);
long sum = 10;
// Initialize dp array with -1
vector<vector<int>> dp;
dp.resize(N + 5);
for(int i = 0; i < N + 5; i++)
for(int j = 0; j < M + 5; j++)
dp[i].push_back(-1);
// Stores maximum sum of M elements
sum += mElementsWithMaxSum(matrix, M,
0, dp);
cout << sum;
}
// Driver Code
int main()
{
// Given N
int N = 3;
// Given M
int M = 4;
// Given matrix
vector<vector<int>> matrix = { { 2, 3, 5 },
{ -1, 7 },
{ 8, 10 } };
// Function call
mElementsWithMaxSumUtil(matrix, M, N);
}
// This code is contributed by grand_master
Java
// Java program for the above approach
import java.util.*;
public class GFG {
// Function to select m elements
// having maximum sum
public static long
mElementsWithMaxSum(long[][] matrix,
int M, int block,
long[][] dp)
{
// Base case
if (block == matrix.length)
return 0;
// If precomputed subproblem occurred
if (dp[block][M] != -1)
return dp[block][M];
// Either skip the current row
long ans
= mElementsWithMaxSum(matrix, M,
block + 1, dp);
// Iterate through all the possible
// segments of current row
for (int i = 0;
i < matrix[block].length; i++) {
for (int j = i;
j < matrix[block].length; j++) {
// Check if it is possible to select
// elements from i to j
if (j - i + 1 <= M) {
// Compute the sum of i to j as
// calculated
ans = Math.max(
ans,
matrix[block][j]
- ((i - 1) >= 0
? matrix[block][i - 1]
: 0)
+ mElementsWithMaxSum(
matrix, M - j + i - 1,
block + 1, dp));
}
}
}
// Store the computed answer and return
return dp[block][M] = ans;
}
// Function to precompute the prefix sum
// for every row of the matrix
public static void
preComputing(long[][] matrix, int N)
{
// Preprocessing to calculate sum from i to j
for (int i = 0;
i < N; i++) {
for (int j = 0;
j < matrix[i].length; j++) {
matrix[i][j]
= (j > 0
? matrix[i][j - 1] : 0)
+ matrix[i][j];
}
}
}
// Utility function to select m elements having
// maximum sum
public static void
mElementsWithMaxSumUtil(long[][] matrix,
int M, int N)
{
// Preprocessing step
preComputing(matrix, N);
// Initialize dp array with -1
long dp[][] = new long[N + 5][M + 5];
for (long i[] : dp)
Arrays.fill(i, -1);
// Stores maximum sum of M elements
long sum = mElementsWithMaxSum(matrix, M,
0, dp);
// Print the sum
System.out.print(sum);
}
// Driver Code
public static void main(String args[])
{
// Given N
int N = 3;
// Given M
int M = 4;
// Given matrix
long[][] matrix
= { { 2, 3, 5 }, { -1, 7 },
{ 8, 10 } };
// Function Call
mElementsWithMaxSumUtil(matrix, M, N);
}
}
Python3
# Python3 program for the above approach # Function to select m elements # having maximum sum def mElementsWithMaxSum(matrix, M, block, dp): # Base case if block == len(matrix): return 0 # If precomputed subproblem occurred if (dp[block][M] != -1): return dp[block][M] # Either skip the current row ans = mElementsWithMaxSum(matrix, M, block + 1, dp) # Iterate through all the possible # segments of current row for i in range(len(matrix[block])): for j in range(i, len(matrix[block])): # Check if it is possible to select # elements from i to j if (j - i + 1 <= M): # Compute the sum of i to j as # calculated x = 0 if i - 1 >= 0: x = matrix[block][i - 1] ans = max(ans, matrix[block][j] - x + mElementsWithMaxSum(matrix, M - j + i - 1, block + 1, dp)) # Store the computed answer and return dp[block][M] = ans return ans # Function to precompute the prefix sum # for every row of the matrix def preComputing(matrix, N): # Preprocessing to calculate sum from i to j for i in range(N): for j in range(len(matrix[i])): if j > 0: matrix[i][j] = matrix[i][j - 1] return matrix # Utility function to select m elements having # maximum sum def mElementsWithMaxSumUtil(matrix, M, N): # Preprocessing step matrix = preComputing(matrix, N) sum = 20 # Initialize dp array with -1 dp = [[-1 for i in range(M + 5)] for i in range(N + 5)] # Stores maximum sum of M elements sum += mElementsWithMaxSum(matrix, M, 0, dp) print(sum) # Driver Code if __name__ == '__main__': # Given N N = 3 # Given M M = 4 # Given matrix matrix = [ [ 2, 3, 5 ], [ -1, 7 ], [ 8, 10 ] ] # Function call mElementsWithMaxSumUtil(matrix, M, N) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
// Function to select m elements
// having maximum sum
public static int mElementsWithMaxSum(int[,] matrix,
int M, int block,
int[,] dp)
{
// Base case
if (block == matrix.GetLength(0))
return 0;
// If precomputed subproblem occurred
if (dp[block, M] != -1)
return dp[block, M];
// Either skip the current row
int ans = mElementsWithMaxSum(matrix, M,
block + 1, dp);
// Iterate through all the possible
// segments of current row
for (int i = 0;
i < GetRow(matrix, block).Length; i++)
{
for (int j = i;
j < GetRow(matrix, block).Length; j++)
{
// Check if it is possible to select
// elements from i to j
if (j - i + 1 <= M)
{
// Compute the sum of i to j as
// calculated
ans = Math.Max(ans, matrix[block, j] -
((i - 1) >= 0 ?
matrix[block, i - 1] : 0) +
mElementsWithMaxSum(matrix,
M - j + i - 1,
block + 1, dp));
}
}
}
// Store the computed answer and return
return dp[block, M] = ans;
}
// Function to precompute the prefix sum
// for every row of the matrix
public static void preComputing(int[,] matrix,
int N)
{
// Preprocessing to calculate sum from i to j
for (int i = 0; i < N; i++)
{
for (int j = 0;
j < GetRow(matrix, i).Length; j++)
{
matrix[i, j] = (j > 0 ? matrix[i, j - 1] : 0) +
matrix[i, j];
}
}
}
// Utility function to select
// m elements having maximum sum
public static void mElementsWithMaxSumUtil(int[,] matrix,
int M, int N)
{
// Preprocessing step
preComputing(matrix, N);
// Initialize dp array with -1
int [,]dp = new int[N + 5, M + 5];
for(int i = 0; i < N + 5; i++)
{
for (int j = 0; j < M + 5; j++)
{
dp[i, j] = -1;
}
}
// Stores maximum sum of M elements
int sum = mElementsWithMaxSum(matrix, M,
0, dp);
// Print the sum
Console.Write(sum);
}
public static int[] GetRow(int[,] matrix,
int row)
{
var rowLength = matrix.GetLength(1);
var rowVector = new int[rowLength];
for (var i = 0; i < rowLength; i++)
rowVector[i] = matrix[row, i];
return rowVector;
}
// Driver Code
public static void Main(String []args)
{
// Given N
int N = 3;
// Given M
int M = 4;
// Given matrix
int[,] matrix = {{2, 3, 5},
{-1, 7,0},
{8, 10, 0}};
// Function Call
mElementsWithMaxSumUtil(matrix, M, N);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function to select m elements
// having maximum sum
function mElementsWithMaxSum(matrix, M, block, dp)
{
// Base case
if (block == matrix.length)
return 0;
// If precomputed subproblem occurred
if (dp[block][M] != -1)
return dp[block][M];
// Either skip the current row
var ans = mElementsWithMaxSum(matrix, M,
block + 1, dp);
// Iterate through all the possible
// segments of current row
for(var i = 0;
i < matrix[block].length; i++)
{
for(var j = i;
j < matrix[block].length; j++)
{
// Check if it is possible to select
// elements from i to j
if (j - i + 1 <= M)
{
// Compute the sum of i to j as
// calculated
ans = Math.max(ans, matrix[block][j] -
((i - 1) >= 0 ?
matrix[block][i - 1] : 0) +
mElementsWithMaxSum(matrix,
M - j +
i - 1,
block + 1, dp));
}
}
}
// Store the computed answer and return
return dp[block][M] = ans;
}
// Function to precompute the prefix sum
// for every row of the matrix
function preComputing(matrix, N)
{
// Preprocessing to calculate sum from i to j
for(var i = 0; i < N; i++)
{
for(var j = 0; j < matrix[i].length; j++)
{
matrix[i][j] = (j > 0 ?
matrix[i][j - 1] : 0) +
matrix[i][j];
}
}
}
// Utility function to select m elements having
// maximum sum
function mElementsWithMaxSumUtil(matrix, M, N)
{
// Preprocessing step
preComputing(matrix, N);
// Initialize dp array with -1
var dp = Array.from(Array(N+5), ()=> Array(M+5).fill(-1));
// Stores maximum sum of M elements
var sum = mElementsWithMaxSum(matrix, M,
0, dp);
document.write( sum);
}
// Driver Code
// Given N
var N = 3;
// Given M
var M = 4;
// Given matrix
var matrix = [ [ 2, 3, 5 ],
[ -1, 7 ],
[ 8, 10 ] ];
// Function call
mElementsWithMaxSumUtil(matrix, M, N);
// This code is contributed by noob2000.
</script>
Producción:
30
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA