Suma máxima posible de Matrix dada al realizar operaciones dadas

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

  1. Inicialice dos variables r1 y r2 para almacenar la suma máxima para la y la fila respectivamente.
  2. 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]) .
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *