Dada una array arr[][] de dimensiones 2 * N , la tarea es maximizar la suma posible seleccionando como máximo un elemento de cada columna de modo que no se elijan dos elementos consecutivos de la misma fila.
Ejemplos:
Entrada: arr[][] = {{1, 50, 21, 5}, {2, 10, 10, 5}}
Salida: 67
Explicación: Elementos arr[1][0]( = 2), arr[0 Se pueden elegir ][1]( = 50), arr[0][2]( = 10) y arr[0][3]( = 5). Por lo tanto, suma = 2 + 50 + 10 + 5 = 67.Entrada: arr[][] = {{9, 5, 3, 7, 3}, {50, 8, 1, 50, 5}}
Salida: 108
Explicación: Elementos arr[1][0]( = 50) , arr[0][1]( = 5), arr[1][3]( = 50) y arr[0][4]( = 3) se pueden elegir. Por lo tanto, suma = 50 + 5 + 50 + 3 = 108.
Enfoque de programación dinámica : el problema se puede resolver mediante programación dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp[][] para almacenar los siguientes estados de transición:
dp[0][i] = max(dp[1][i+1], dp[0][i+2]) + arr[0][i]
dp[1][i] = max(dp[ 0][i+1], dp[1][i+2]) + arr[1][i]
donde, dp[j][i] almacena la suma máxima posible para llegar a la celda arr[j][i] comenzando desde la última columna donde 0 <= i < N y 0 <= j < 2.Caso base:
dp[0][N-1] = arr[0][N-1]
dp[1][N-1] = arr[1][N-1]
- Recorra desde (N – 2) columna a la columna 0 y para cada fila, actualice dp[j][i] como dp[j][i] = max(dp[(j ^ 1)][i+1 ], dp[j][i+2]) + arr[j][i] donde ^ representa Bitwise XOR .
- Después de completar el recorrido, imprima max(dp[0][0], dp[1][0]) como la suma máxima posible.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <vector>
using namespace std;
// Function to print the maximum sum
void maxSum(vector<vector<int> > arr,
int n, int m)
{
// Dp table
vector<vector<int> > dp(n);
// Initializing dp array with 0s
for (int i = 0; i < 2; i++) {
dp[i] = vector<int>(m);
for (int j = 0; j < m; j++) {
dp[i][j] = 0;
}
}
// Base case
dp[0][m - 1] = arr[0][m - 1];
dp[1][m - 1] = arr[1][m - 1];
// Traverse each column
for (int j = m - 2; j >= 0; j--) {
// Update answer for both rows
for (int i = 0; i < 2; i++) {
if (i == 1) {
dp[i][j] = max(
arr[i][j] + dp[0][j + 1],
arr[i][j] + dp[0][j + 2]);
}
else {
dp[i][j] = max(
arr[i][j] + dp[1][j + 1],
arr[i][j] + dp[1][j + 2]);
}
}
}
// Print the maximum sum
cout << max(dp[0][0], dp[1][0]);
}
// Driver Code
int main()
{
// Given array
vector<vector<int> > arr
= { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Number of Columns
int N = arr[0].size();
// Function calls
maxSum(arr, 2, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to print the maximum sum
static void maxSum(int[][] arr, int n, int m)
{
// Dp table
int[][] dp = new int[n][m + 1];
// Initializing dp array with 0s
for(int i = 0; i < 2; i++)
{
for(int j = 0; j <= m; j++)
{
dp[i][j] = 0;
}
}
// Base case
dp[0][m - 1] = arr[0][m - 1];
dp[1][m - 1] = arr[1][m - 1];
// Traverse each column
for(int j = m - 2; j >= 0; j--)
{
// Update answer for both rows
for (int i = 0; i < 2; i++)
{
if (i == 1)
{
dp[i][j] = Math.max(
arr[i][j] + dp[0][j + 1],
arr[i][j] + dp[0][j + 2]);
}
else
{
dp[i][j] = Math.max(
arr[i][j] + dp[1][j + 1],
arr[i][j] + dp[1][j + 2]);
}
}
}
// Print the maximum sum
System.out.println(Math.max(dp[0][0],
dp[1][0]));
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[][] arr = { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Number of Columns
int N = arr[0].length;
// Function calls
maxSum(arr, 2, N);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach
# Function to print the maximum sum
def maxSum(arr, n, m):
# Dp table
dp = [[0 for i in range(m + 1)]
for i in range(2)]
# Initializing dp array with 0s
# for (i = 0 i < 2 i++) {
# dp[i] = vector<int>(m)
# for (j = 0 j < m j++) {
# dp[i][j] = 0
# }
# }
# Base case
dp[0][m - 1] = arr[0][m - 1]
dp[1][m - 1] = arr[1][m - 1]
# Traverse each column
for j in range(m - 2, -1, -1):
# Update answer for both rows
for i in range(2):
if (i == 1):
dp[i][j] = max(arr[i][j] + dp[0][j + 1],
arr[i][j] + dp[0][j + 2])
else:
dp[i][j] = max(arr[i][j] + dp[1][j + 1],
arr[i][j] + dp[1][j + 2])
# Print the maximum sum
print(max(dp[0][0], dp[1][0]))
# Driver Code
if __name__ == '__main__':
# Given array
arr = [ [ 1, 50, 21, 5 ],
[ 2, 10, 10, 5 ] ]
# Number of Columns
N = len(arr[0])
# Function calls
maxSum(arr, 2, N)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Function to print the maximum sum
static void maxSum(int[, ] arr, int n, int m)
{
// Dp table
int[, ] dp = new int[n, m + 1];
// Initializing dp array with 0s
for(int i = 0; i < 2; i++)
{
for(int j = 0; j <= m; j++)
{
dp[i, j] = 0;
}
}
// Base case
dp[0, m - 1] = arr[0, m - 1];
dp[1, m - 1] = arr[1, m - 1];
// Traverse each column
for(int j = m - 2; j >= 0; j--)
{
// Update answer for both rows
for(int i = 0; i < 2; i++)
{
if (i == 1)
{
dp[i, j] = Math.Max(
arr[i, j] + dp[0, j + 1],
arr[i, j] + dp[0, j + 2]);
}
else
{
dp[i, j] = Math.Max(
arr[i, j] + dp[1, j + 1],
arr[i, j] + dp[1, j + 2]);
}
}
}
// Print the maximum sum
Console.WriteLine(Math.Max(dp[0, 0],
dp[1, 0]));
}
// Driver Code
public static void Main()
{
// Given array
int[, ] arr = { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Number of Columns
int N = arr.GetLength(1);
// Function calls
maxSum(arr, 2, N);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to print the maximum sum
function maxSum(arr, n, m)
{
// Dp table
let dp = new Array(n);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Initializing dp array with 0s
for(let i = 0; i < 2; i++)
{
for(let j = 0; j <= m; j++)
{
dp[i][j] = 0;
}
}
// Base case
dp[0][m - 1] = arr[0][m - 1];
dp[1][m - 1] = arr[1][m - 1];
// Traverse each column
for(let j = m - 2; j >= 0; j--)
{
// Update answer for both rows
for (let i = 0; i < 2; i++)
{
if (i == 1)
{
dp[i][j] = Math.max(
arr[i][j] + dp[0][j + 1],
arr[i][j] + dp[0][j + 2]);
}
else
{
dp[i][j] = Math.max(
arr[i][j] + dp[1][j + 1],
arr[i][j] + dp[1][j + 2]);
}
}
}
// Print the maximum sum
document.write(Math.max(dp[0][0],
dp[1][0]));
}
// Driver Code
// Given array
let arr = [[ 1, 50, 21, 5 ],
[ 2, 10, 10, 5 ]];
// Number of Columns
let N = arr[0].length;
// Function calls
maxSum(arr, 2, N);
</script>
Producción:
67
Complejidad temporal: O(N), donde N es el número de columnas.
Espacio Auxiliar: O(N)
Enfoque eficiente: siga los pasos a continuación para optimizar el enfoque anterior
- Inicialice dos variables r1 y r2 para almacenar la suma máxima para la 1ª y la 2ª fila respectivamente.
- Recorra la longitud de la fila, es decir, de 0 a N – 1 y para cada elemento arr[i] , actualice r1 como r1 = max(r1, r2 + arr[0][i]) y r2 como r2 = max(r2 , r1 + arr[1][i]) .
- Después de atravesar, imprima max(r1, r2) como la suma máxima.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the maximum sum
// possible by selecting at most one
// element from each column such that
// no consecutive pairs are selected
// from a single row
void maxSum(vector<vector<int> > arr, int n)
{
// Initialize variables
int r1 = 0, r2 = 0;
// Traverse each column
for(int i = 0; i < n; i++)
{
// r1, r2 = max(r1, r2 + arr[0][i]),
// max(r2, r1 + arr[1][i])
int temp = r1;
r1 = max(r1, r2 + arr[0][i]);
r2 = max(r2, temp + arr[1][i]);
}
// Print answer
cout << max(r1, r2);
}
// Driver Code
int main()
{
vector<vector<int>> arr = { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Numberof columns
int n = arr[0].size();
maxSum(arr, n);
return 0;
}
// This code is contributed by akhilsaini
Java
// Java code for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to print the maximum sum
// possible by selecting at most one
// element from each column such that
// no consecutive pairs are selected
// from a single row
static void maxSum(int[][] arr, int n)
{
// Initialize variables
int r1 = 0, r2 = 0;
// Traverse each column
for(int i = 0; i < n; i++)
{
int temp = r1;
r1 = Math.max(r1, r2 + arr[0][i]);
r2 = Math.max(r2, temp + arr[1][i]);
}
// Print answer
System.out.println(Math.max(r1, r2));
}
// Driver Code
public static void main(String args[])
{
int[][] arr = { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Numberof columns
int n = arr[0].length;
maxSum(arr, n);
}
}
// This code is contributed by akhilsaini
Python
# Python code for the above approach # Function to print the maximum sum # possible by selecting at most one # element from each column such that # no consecutive pairs are selected # from a single row def maxSum(arr, n): # Initialize variables r1 = r2 = 0 # Traverse each column for i in range(n): r1, r2 = max(r1, r2 + arr[0][i]), max(r2, r1 + arr[1][i]) # Print answer print(max(r1, r2)) # Driver Code arr = [[1, 50, 21, 5], [2, 10, 10, 5]] # Numberof columns n = len(arr[0]) maxSum(arr, n)
C#
// C# code for the above approach
using System;
class GFG{
// Function to print the maximum sum
// possible by selecting at most one
// element from each column such that
// no consecutive pairs are selected
// from a single row
static void maxSum(int[, ] arr, int n)
{
// Initialize variables
int r1 = 0, r2 = 0;
// Traverse each column
for(int i = 0; i < n; i++)
{
int temp = r1;
r1 = Math.Max(r1, r2 + arr[0, i]);
r2 = Math.Max(r2, temp + arr[1, i]);
}
// Print answer
Console.WriteLine(Math.Max(r1, r2));
}
// Driver Code
public static void Main()
{
int[, ] arr = { { 1, 50, 21, 5 },
{ 2, 10, 10, 5 } };
// Numberof columns
int n = arr.GetLength(1);
maxSum(arr, n);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript code for the above approach
// Function to print the maximum sum
// possible by selecting at most one
// element from each column such that
// no consecutive pairs are selected
// from a single row
function maxSum(arr , n) {
// Initialize variables
var r1 = 0, r2 = 0;
// Traverse each column
for (i = 0; i < n; i++) {
var temp = r1;
r1 = Math.max(r1, r2 + arr[0][i]);
r2 = Math.max(r2, temp + arr[1][i]);
}
// Print answer
document.write(Math.max(r1, r2));
}
// Driver Code
var arr = [ [ 1, 50, 21, 5 ],
[ 2, 10, 10, 5 ] ];
// Numberof columns
var n = arr[0].length;
maxSum(arr, n);
// This code is contributed by todaysgaurav
</script>
Producción:
67
Complejidad temporal: O(N), donde N es el número de columnas.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por RohitOberoi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA