Suma máxima en una cuadrícula de 2 xn tal que no haya dos elementos adyacentes

Dada una cuadrícula rectangular de dimensión 2 x n. Necesitamos encontrar la suma máxima tal que no haya dos números elegidos adyacentes, vertical, diagonal u horizontalmente. 
Ejemplos: 

Input: 1 4 5
       2 0 0
Output: 7
If we start from 1 then we can add only 5 or 0. 
So max_sum = 6 in this case.
If we select 2 then also we can add only 5 or 0.
So max_sum = 7 in this case.
If we select from 4 or 0  then there is no further 
elements can be added.
So, Max sum is 7.

Input: 1 2 3 4 5
       6 7 8 9 10
Output: 24

Acercarse:

Este problema es una extensión de la suma máxima tal que no hay dos elementos adyacentes . Lo único que se puede cambiar es tomar un elemento máximo de ambas filas de una columna en particular. Recorremos columna por columna y mantenemos la suma máxima considerando dos casos. 
1) Se incluye un elemento de la columna actual. En este caso, tomamos un máximo de dos elementos en la columna actual. 
2) Se excluye (o no se incluye) un elemento de la columna actual.
A continuación se muestra la implementación de los pasos anteriores. 

// C++ program to find maximum sum in a grid such that
// no two elements are adjacent.
#include<bits/stdc++.h>
#define MAX 1000
using namespace std;
 
// Function to find max sum without adjacent
int maxSum(int grid[2][MAX], int n)
{
    // Sum including maximum element of first column
    int incl = max(grid[0][0], grid[1][0]);
 
    // Not including first column's element
    int excl = 0, excl_new;
 
    // Traverse for further elements
    for (int i = 1; i<n; i++ )
    {
        // Update max_sum on including or excluding
        // of previous column
        excl_new = max(excl, incl);
 
        // Include current column. Add maximum element
        // from both row of current column
        incl = excl + max(grid[0][i], grid[1][i]);
 
        // If current column doesn't to be included
        excl = excl_new;
    }
 
    // Return maximum of excl and incl
    // As that will be the maximum sum
    return max(excl, incl);
}
 
// Driver code
int main()
{
    int grid[2][MAX] = {{ 1, 2, 3, 4, 5},
                        { 6, 7, 8, 9, 10}};
 
    int n = 5;
    cout << maxSum(grid, n);
 
    return 0;
}

// C program to find maximum sum in a grid such that
// no two elements are adjacent.
#include <stdio.h>
 
#define MAX 1000
 
// Function to find max sum without adjacent
int maxSum(int grid[2][MAX], int n)
{
  // Sum including maximum element of first column
  int max = grid[0][0];
  if(max < grid[1][0])
    max = grid[1][0];
  int incl = max;
 
  // Not including first column's element
  int excl = 0, excl_new;
 
  // Traverse for further elements
  for (int i = 1; i<n; i++ )
  {
    // Update max_sum on including or excluding
    // of previous column
    max = excl;
    if(max < incl)
      max = incl;
    excl_new = max;
 
    // Include current column. Add maximum element
    // from both row of current column
    max = grid[0][i];
    if(max < grid[1][i])
      max = grid[1][i];
    incl = excl + max;
 
    // If current column doesn't to be included
    excl = excl_new;
  }
 
  // Return maximum of excl and incl
  // As that will be the maximum sum
  max = excl;
  if(max < incl)
    max = incl;
  return max;
}
 
// Driver code
int main()
{
  int grid[2][MAX] = {{ 1, 2, 3, 4, 5},
                      { 6, 7, 8, 9, 10}};
 
  int n = 5;
  printf("%d",maxSum(grid, n));
 
  return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java Code for Maximum sum in a 2 x n grid
// such that no two elements are adjacent
import java.util.*;
 
class GFG {
     
    // Function to find max sum without adjacent
    public static int maxSum(int grid[][], int n)
    {
        // Sum including maximum element of first
        // column
        int incl = Math.max(grid[0][0], grid[1][0]);
      
        // Not including first column's element
        int excl = 0, excl_new;
      
        // Traverse for further elements
        for (int i = 1; i < n; i++ )
        {
            // Update max_sum on including or
            // excluding of previous column
            excl_new = Math.max(excl, incl);
      
            // Include current column. Add maximum element
            // from both row of current column
            incl = excl + Math.max(grid[0][i], grid[1][i]);
      
            // If current column doesn't to be included
            excl = excl_new;
        }
      
        // Return maximum of excl and incl
        // As that will be the maximum sum
        return Math.max(excl, incl);
    }
     
    /* Driver program to test above function */
    public static void main(String[] args)
    {
         int grid[][] = {{ 1, 2, 3, 4, 5},
                         { 6, 7, 8, 9, 10}};
 
         int n = 5;
         System.out.println(maxSum(grid, n));
    }
  }
// This code is contributed by Arnav Kr. Mandal.

# Python3 program to find maximum sum in a grid such that
# no two elements are adjacent.
 
# Function to find max sum without adjacent
def maxSum(grid, n) :
     
    # Sum including maximum element of first column
    incl = max(grid[0][0], grid[1][0])
 
    # Not including first column's element
    excl = 0 
 
    # Traverse for further elements
    for i in range(1, n) :
         
        # Update max_sum on including or excluding
        # of previous column
        excl_new = max(excl, incl)
 
        # Include current column. Add maximum element
        # from both row of current column
        incl = excl + max(grid[0][i], grid[1][i])
 
        # If current column doesn't to be included
        excl = excl_new
 
    # Return maximum of excl and incl
    # As that will be the maximum sum
    return max(excl, incl)
 
 
# Driver code
if __name__ == "__main__" :
  
    grid = [ [ 1, 2, 3, 4, 5],
             [ 6, 7, 8, 9, 10] ]
    n = 5
    print(maxSum(grid, n))
 
// This code is contributed by Ryuga

// C# program Code for Maximum sum
// in a 2 x n grid such that no two
// elements are adjacent
using System;   
 
class GFG
{
 
// Function to find max sum
// without adjacent
public static int maxSum(int [,]grid, int n)
{
    // Sum including maximum element
    // of first column
    int incl = Math.Max(grid[0, 0],
                        grid[1, 0]);
 
    // Not including first column's
    // element
    int excl = 0, excl_new;
 
    // Traverse for further elements
    for (int i = 1; i < n; i++ )
    {
        // Update max_sum on including or
        // excluding of previous column
        excl_new = Math.Max(excl, incl);
 
        // Include current column. Add
        // maximum element from both
        // row of current column
        incl = excl + Math.Max(grid[0, i],
                               grid[1, i]);
 
        // If current column doesn't
        // to be included
        excl = excl_new;
    }
 
    // Return maximum of excl and incl
    // As that will be the maximum sum
    return Math.Max(excl, incl);
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]grid = {{ 1, 2, 3, 4, 5},
                   { 6, 7, 8, 9, 10}};
 
    int n = 5;
    Console.Write(maxSum(grid, n));
}
}
 
// This code is contributed
// by PrinciRaj1992

<?php
// PHP program to find maximum sum
// in a grid such that no two elements
// are adjacent.
 
// Function to find max sum
// without adjacent
function maxSum($grid, $n)
{
    // Sum including maximum element
    // of first column
    $incl = max($grid[0][0], $grid[1][0]);
 
    // Not including first column's element
    $excl = 0;
    $excl_new;
 
    // Traverse for further elements
    for ($i = 1; $i < $n; $i++ )
    {
        // Update max_sum on including or
        // excluding of previous column
        $excl_new = max($excl, $incl);
 
        // Include current column. Add maximum
        // element from both row of current column
        $incl = $excl + max($grid[0][$i],
                            $grid[1][$i]);
 
        // If current column doesn't
        // to be included
        $excl = $excl_new;
    }
 
    // Return maximum of excl and incl
    // As that will be the maximum sum
    return max($excl, $incl);
}
 
// Driver code
$grid = array(array(1, 2, 3, 4, 5),
              array(6, 7, 8, 9, 10));
 
$n = 5;
echo maxSum($grid, $n);
 
// This code is contributed by Sachin..
?>

<script>
 
// JavaScript program Code for Maximum sum
// in a 2 x n grid such that no two
// elements are adjacent
 
// Function to find max sum
// without adjacent
function maxSum(grid,n)
{
    // Sum including maximum element
    // of first column
   let incl = Math.max(grid[0][0], grid[1][0]);
 
    // Not including first column's
    // element
   let excl = 0, excl_new;
 
    // Traverse for further elements
    for (let i = 1; i < n; i++ )
    {
        // Update max_sum on including or
        // excluding of previous column
        excl_new = Math.max(excl, incl);
 
        // Include current column. Add
        // maximum element from both
        // row of current column
        incl = excl + Math.max(grid[0][i], grid[1][i]);
 
        // If current column doesn't
        // to be included
        excl = excl_new;
    }
 
    // Return maximum of excl and incl
    // As that will be the maximum sum
    return Math.max(excl, incl);
}
 
// Driver Code
 
let grid =[[ 1, 2, 3, 4, 5], [6, 7, 8, 9, 10]];
 
let n = 5;
document.write(maxSum(grid, n));
 
 
// This code is contributed
// by PrinciRaj1992
 
 
</script>

Producción: 

24

Complejidad de tiempo: O (n) donde n es el número de elementos en una array dada. Como estamos usando un bucle para atravesar N veces, nos costará O (N) tiempo 
Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional.
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.