Maximice la suma eligiendo elementos de diferentes secciones de una array

Dada una array de N filas y M columnas. Se da que M es múltiplo de 3. Las columnas se dividen en 3 tramos, el primer tramo es de 0 a m/3-1, el segundo tramo es de m/3 a 2m/3-1 y el tercero es de 2m/3 a m. La tarea es elegir un solo elemento de cada fila y, en filas adyacentes, no podemos seleccionar de la misma sección. Tenemos que maximizar la suma de los elementos elegidos. 
Ejemplos: 

Entrada: mat[][] = { 
{1, 3, 5, 2, 4, 6}, 
{6, 4, 5, 1, 3, 2}, 
{1, 3, 5, 2, 4, 6} , 
{6, 4, 5, 1, 3, 2}, 
{6, 4, 5, 1, 3, 2}, 
{1, 3, 5, 2, 4, 6}} 
Salida: 35

Entrada: mat[][] = { 
{1, 2, 3}, 
{3, 2, 1}, 
{5, 4, 2} 
Salida: 10  

Enfoque: el problema se puede resolver utilizando una solución de programación dinámica almacenando los subproblemas y reutilizándolos. Cree una array dp[][] donde dp[i][0] representa la suma de los elementos de las filas de 0 a i tomando elementos de la sección 1 . Del mismo modo, para dp[i][1] y dp[i][2] . Por lo tanto, imprima max(dp[n – 1][0], dp[n – 1][1], dp[n – 1][2] . 
A continuación se muestra la implementación del enfoque anterior: 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
const int n = 6, m = 6;
 
// Function to find the maximum value
void maxSum(long arr[n][m])
{
    // Dp table
    long dp[n + 1][3] = { 0 };
 
    // Fill the dp in bottom
    // up manner
    for (int i = 0; i < n; i++) {
 
        // Maximum of the three sections
        long m1 = 0, m2 = 0, m3 = 0;
 
        for (int j = 0; j < m; j++) {
 
            // Maximum of the first section
            if ((j / (m / 3)) == 0) {
                m1 = max(m1, arr[i][j]);
            }
 
            // Maximum of the second section
            else if ((j / (m / 3)) == 1) {
                m2 = max(m2, arr[i][j]);
            }
 
            // Maximum of the third section
            else if ((j / (m / 3)) == 2) {
                m3 = max(m3, arr[i][j]);
            }
        }
 
        // If we choose element from section 1,
        // we cannot have selection from same section
        // in adjacent rows
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + m1;
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + m2;
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + m3;
    }
 
    // Print the maximum sum
    cout << max(max(dp[n][0], dp[n][1]), dp[n][2]) << '\n';
}
 
// Driver code
int main()
{
 
    long arr[n][m] = { { 1, 3, 5, 2, 4, 6 },
                       { 6, 4, 5, 1, 3, 2 },
                       { 1, 3, 5, 2, 4, 6 },
                       { 6, 4, 5, 1, 3, 2 },
                       { 6, 4, 5, 1, 3, 2 },
                       { 1, 3, 5, 2, 4, 6 } };
 
    maxSum(arr);
 
    return 0;
}

// Java program for the above approach
class GFG
{
 
static int n = 6, m = 6;
 
// Function to find the maximum value
static void maxSum(long arr[][])
{
    // Dp table
    long [][]dp= new long[n + 1][3];
 
    // Fill the dp in bottom
    // up manner
    for (int i = 0; i < n; i++)
    {
 
        // Maximum of the three sections
        long m1 = 0, m2 = 0, m3 = 0;
 
        for (int j = 0; j < m; j++)
        {
 
            // Maximum of the first section
            if ((j / (m / 3)) == 0)
            {
                m1 = Math.max(m1, arr[i][j]);
            }
 
            // Maximum of the second section
            else if ((j / (m / 3)) == 1)
            {
                m2 = Math.max(m2, arr[i][j]);
            }
 
            // Maximum of the third section
            else if ((j / (m / 3)) == 2)
            {
                m3 = Math.max(m3, arr[i][j]);
            }
        }
 
        // If we choose element from section 1,
        // we cannot have selection from same section
        // in adjacent rows
        dp[i + 1][0] = Math.max(dp[i][1], dp[i][2]) + m1;
        dp[i + 1][1] = Math.max(dp[i][0], dp[i][2]) + m2;
        dp[i + 1][2] = Math.max(dp[i][1], dp[i][0]) + m3;
    }
 
    // Print the maximum sum
    System.out.print(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2]) + "\n");
}
 
// Driver code
public static void main(String[] args)
{
 
    long arr[][] = { { 1, 3, 5, 2, 4, 6 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 1, 3, 5, 2, 4, 6 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 1, 3, 5, 2, 4, 6 } };
 
    maxSum(arr);
}
}
 
// This code is contributed by PrinciRaj1992

# Python3 program for the above approach
import numpy as np
n = 6; m = 6;
 
# Function to find the maximum value
def maxSum(arr) :
 
    # Dp table
    dp = np.zeros((n + 1, 3));
 
    # Fill the dp in bottom
    # up manner
    for i in range(n) :
 
        # Maximum of the three sections
        m1 = 0; m2 = 0; m3 = 0;
         
        for j in range(m) :
             
            # Maximum of the first section
            if ((j // (m // 3)) == 0) :
                m1 = max(m1, arr[i][j]);
                 
            # Maximum of the second section
            elif ((j // (m // 3)) == 1) :
                m2 = max(m2, arr[i][j]);
                 
            # Maximum of the third section
            elif ((j // (m // 3)) == 2) :
                m3 = max(m3, arr[i][j]);
                 
        # If we choose element from section 1,
        # we cannot have selection from same section
        # in adjacent rows
        dp[i + 1][0] = max(dp[i][1], dp[i][2]) + m1;
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + m2;
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + m3;
 
    # Print the maximum sum
    print(max(max(dp[n][0], dp[n][1]), dp[n][2]));
 
# Driver code
if __name__ == "__main__" :
 
    arr = [[ 1, 3, 5, 2, 4, 6 ],
           [ 6, 4, 5, 1, 3, 2 ],
           [ 1, 3, 5, 2, 4, 6 ],
           [ 6, 4, 5, 1, 3, 2 ],
           [ 6, 4, 5, 1, 3, 2 ],
           [ 1, 3, 5, 2, 4, 6 ]];
 
    maxSum(arr);
     
# This code is contributed by AnkitRai01

// C# program for the above approach
using System;
 
class GFG
{
static int n = 6, m = 6;
 
// Function to find the maximum value
static void maxSum(long [,]arr)
{
    // Dp table
    long [,]dp = new long[n + 1, 3];
 
    // Fill the dp in bottom
    // up manner
    for (int i = 0; i < n; i++)
    {
 
        // Maximum of the three sections
        long m1 = 0, m2 = 0, m3 = 0;
 
        for (int j = 0; j < m; j++)
        {
 
            // Maximum of the first section
            if ((j / (m / 3)) == 0)
            {
                m1 = Math.Max(m1, arr[i, j]);
            }
 
            // Maximum of the second section
            else if ((j / (m / 3)) == 1)
            {
                m2 = Math.Max(m2, arr[i, j]);
            }
 
            // Maximum of the third section
            else if ((j / (m / 3)) == 2)
            {
                m3 = Math.Max(m3, arr[i, j]);
            }
        }
 
        // If we choose element from section 1,
        // we cannot have selection from same section
        // in adjacent rows
        dp[i + 1, 0] = Math.Max(dp[i, 1], dp[i, 2]) + m1;
        dp[i + 1, 1] = Math.Max(dp[i, 0], dp[i, 2]) + m2;
        dp[i + 1, 2] = Math.Max(dp[i, 1], dp[i, 0]) + m3;
    }
 
    // Print the maximum sum
    Console.Write(Math.Max(Math.Max(dp[n, 0],
                                    dp[n, 1]),
                                    dp[n, 2]) + "\n");
}
 
// Driver code
public static void Main(String[] args)
{
    long [,]arr = { { 1, 3, 5, 2, 4, 6 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 1, 3, 5, 2, 4, 6 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 6, 4, 5, 1, 3, 2 },
                    { 1, 3, 5, 2, 4, 6 } };
 
    maxSum(arr);
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program for the above approach
 
const n = 6, m = 6;
 
// Function to find the maximum value
function maxSum(arr)
{
    // Dp table
    const dp = new Array(n+1).fill(0).map(() => new Array(3).fill(0));
 
    // Fill the dp in bottom
    // up manner
    for (var i = 0; i < n; i++) {
 
        // Maximum of the three sections
        var m1 = 0, m2 = 0, m3 = 0;
 
        for (var j = 0; j < m; j++) {
 
            // Maximum of the first section
            if (parseInt(j / (m / 3)) == 0) {
                m1 = Math.max(m1, arr[i][j]);
            }
 
            // Maximum of the second section
            else if (parseInt(j / (m / 3)) == 1) {
                m2 = Math.max(m2, arr[i][j]);
            }
 
            // Maximum of the third section
            else if (parseInt(j / (m / 3)) == 2) {
                m3 = Math.max(m3, arr[i][j]);
            }
        }
 
        // If we choose element from section 1,
        // we cannot have selection from same section
        // in adjacent rows
        dp[i + 1][0] = Math.max(dp[i][1], dp[i][2]) + m1;
        dp[i + 1][1] = Math.max(dp[i][0], dp[i][2]) + m2;
        dp[i + 1][2] = Math.max(dp[i][1], dp[i][0]) + m3;
    }
 
    // Print the maximum sum
    document.write( parseInt(Math.max(Math.max(dp[n][0], dp[n][1]), dp[n][2])) + "<br>");
}
 
arr = [ [ 1, 3, 5, 2, 4, 6 ],
        [ 6, 4, 5, 1, 3, 2 ],
        [ 1, 3, 5, 2, 4, 6 ],
        [ 6, 4, 5, 1, 3, 2 ],
        [ 6, 4, 5, 1, 3, 2 ],
        [ 1, 3, 5, 2, 4, 6 ] ];
 
maxSum(arr);
 
//This code is contributed by SoumikMondal
</script>

35

Complejidad de tiempo: O(n*m), donde n y m son los números de filas y columnas de números en la array.
Espacio auxiliar: O(n*m), ya que estamos usando espacio extra para la array dp .