Maximizar la suma de la subarray superior izquierda NXN de la array 2N X 2N dada

Dada una array de enteros de 2N x 2N . Se le permite invertir cualquier fila o columna cualquier número de veces y en cualquier orden. La tarea es calcular la suma máxima de la subarray NXN superior izquierda, es decir, la suma de elementos de la subarray de (0, 0) a (N – 1, N – 1).

Ejemplos: 

Input : mat[][] = {
                    112, 42, 83, 119,
                    56, 125, 56, 49,
                    15, 78, 101, 43,
                    62, 98, 114, 108
                  }
Output : 414
Given matrix is of size 4 X 4, we need to maximize 
the sum of upper left 2 X 2 matrix i.e 
the sum of mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1].
Following operations maximize the sum:
1. Reverse the column 2,
112, 42, 114, 119,
56, 125, 101, 49,
15, 78, 56, 43,
62, 98, 83, 108

2. Reverse row 0,
119, 114, 42, 112,
56, 125, 101, 49,
15, 78, 56, 43,
62, 98, 83, 108

Sum of upper-left matrix = 119 + 114 + 56 + 125 = 414.

Para maximizar la suma de la subarray superior izquierda, observe, para cada celda de la subarray superior izquierda, hay cuatro candidatos, es decir, las celdas correspondientes en las subarrays superior izquierda, superior derecha, inferior izquierda e inferior derecha con el que se puede intercambiar. 

Ahora, observe para cada celda, donde sea que esté, podemos intercambiarlo con el valor candidato correspondiente en la subarray superior izquierda sin cambiar el orden de las otras celdas en la subarray superior izquierda. El diagrama muestra una instancia donde el máximo el valor de los 4 candidatos está en la subarray superior derecha. Si está en las subarrays inferior izquierda o inferior derecha, primero podemos invertir una fila o columna para colocarla en la subarray superior derecha y luego seguir la misma secuencia de operaciones que se muestra en el diagrama. 

En esta array, digamos que un ₂₆ es el máximo de los 4 candidatos y un ₂₃ debe intercambiarse con un ₂₆ sin cambiar el orden de las celdas en la subarray superior izquierda.

Fila inversa 2, 
 

Columna inversa 2, 
 

Fila inversa 7, 
 

Columna inversa 6, 
 

Fila inversa 2, 
 

A continuación se muestra la implementación de este enfoque: 

// C++ program to find maximum value of top N/2 x N/2
// matrix using row and column reverse operations
#include<bits/stdc++.h>
#define R 4
#define C 4
using namespace std;
 
int maxSum(int mat[R][C])
{
  int sum = 0;
 
  for (int i = 0; i < R/2; i++)
    for (int j = 0; j < C/2; j++)
    {
      int r1 = i;
      int r2 = R - i - 1;
      int c1 = j;
      int c2 = C - j - 1;
       
      // We can replace current cell [i, j]
      // with 4 cells without changing affecting
      // other elements.
      sum += max(max(mat[r1][c1], mat[r1][c2]),
                 max(mat[r2][c1], mat[r2][c2]));
    }
     
    return sum;
}
 
// Driven Program
int main()
{
  int mat[R][C] = {
                    112, 42, 83, 119,
                    56, 125, 56, 49,
                    15, 78, 101, 43,
                    62, 98, 114, 108
                  };
 
  cout << maxSum(mat) << endl;
 
  return 0;
}

// Java program to find maximum value of top N/2 x N/2
// matrix using row and column reverse operations
 
class GFG {
 
    static int maxSum(int mat[][]) {
        int sum = 0;
          int maxI = mat.length;
          int maxIPossible = maxI-1;
          int maxJ = mat[0].length;
          int maxJPossible = maxJ-1;
        for (int i = 0; i < maxI / 2; i++) {
            for (int j = 0; j < maxJ / 2; j++) {
                // We can replace current cell [i, j]
                // with 4 cells without changing affecting
                // other elements.
                sum += Math.max(
                              Math.max(mat[i][j], mat[maxIPossible-i][j]),
                            Math.max(mat[maxIPossible-i][maxJPossible-j], mat[i][maxJPossible-j])
                            );
            }
        }
        return sum;
    }
 
// Driven Program
    public static void main(String[] args) {
        int mat[][] = {
            {112, 42, 83, 119},
            {56, 125, 56, 49},
            {15, 78, 101, 43},
            {62, 98, 114, 108}
        };
 
        System.out.println(maxSum(mat));
 
    }
}
/* This Java code is contributed by Rajput-Ji*/

# Python3 program to find the maximum value
# of top N/2 x N/2 matrix using row and
# column reverse operations
def maxSum(mat):
 
    Sum = 0
    for i in range(0, R // 2):
        for j in range(0, C // 2):
         
            r1, r2 = i, R - i - 1
            c1, c2 = j, C - j - 1
                 
            # We can replace current cell [i, j]
            # with 4 cells without changing/affecting
            # other elements.
            Sum += max(max(mat[r1][c1], mat[r1][c2]),
                       max(mat[r2][c1], mat[r2][c2]))
         
    return Sum
 
# Driver Code
if __name__ == "__main__":
 
    R = C = 4
    mat = [[112, 42, 83, 119],
           [56, 125, 56, 49],
           [15, 78, 101, 43],
           [62, 98, 114, 108]]
 
    print(maxSum(mat))
 
# This code is contributed
# by Rituraj Jain

// C# program to find maximum value
// of top N/2 x N/2 matrix using row
// and column reverse operations
using System;
 
class GFG
{
static int R = 4;
static int C = 4;
 
static int maxSum(int[,] mat)
{
    int sum = 0;
 
    for (int i = 0; i < R / 2; i++)
    {
        for (int j = 0; j < C / 2; j++)
        {
            int r1 = i;
            int r2 = R - i - 1;
            int c1 = j;
            int c2 = C - j - 1;
 
            // We can replace current cell [i, j]
            // with 4 cells without changing affecting
            // other elements.
            sum += Math.Max(Math.Max(mat[r1,c1], mat[r1,c2]),
                            Math.Max(mat[r2,c1], mat[r2,c2]));
        }
    }
    return sum;
}
 
// Driven Code
public static void Main()
{
    int[,] mat =
    {
        {112, 42, 83, 119},
        {56, 125, 56, 49},
        {15, 78, 101, 43},
        {62, 98, 114, 108}
    };
 
    Console.Write(maxSum(mat));
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to find maximum value
// of top N/2 x N/2 matrix using row
// and column reverse operations
 
function maxSum($mat)
{
    $R = 4; $C = 4;
    $sum = 0;
 
    for ($i = 0; $i < $R / 2; $i++)
        for ($j = 0; $j < $C / 2; $j++)
        {
            $r1 = $i;
            $r2 = $R - $i - 1;
            $c1 = $j;
            $c2 = $C - $j - 1;
             
            // We can replace current cell [i, j]
            // with 4 cells without changing
            // affecting other elements.
            $sum += max(max($mat[$r1][$c1],
                            $mat[$r1][$c2]),
                        max($mat[$r2][$c1],
                            $mat[$r2][$c2]));
        }
         
        return $sum;
}
 
// Driver Code
$mat = array(array(112, 42, 83, 119),
             array(56, 125, 56, 49),
             array(15, 78, 101, 43),
             array(62, 98, 114, 108));
 
echo maxSum($mat) . "\n";
 
// This code is contributed
// by Mukul Singh
?>

<script>
// Javascript program to find maximum value of top N/2 x N/2
// matrix using row and column reverse operations
     
    let R = 4;
    let C = 4;
     
    function maxSum(mat)
    {
        let sum = 0;
   
        for (let i = 0; i < R / 2; i++) {
            for (let j = 0; j < C / 2; j++) {
                let r1 = i;
                let r2 = R - i - 1;
                let c1 = j;
                let c2 = C - j - 1;
   
                // We can replace current cell [i, j]
                // with 4 cells without changing affecting
                // other elements.
                sum += Math.max(Math.max(mat[r1][c1], mat[r1][c2]),
                        Math.max(mat[r2][c1], mat[r2][c2]));
            }
        }
   
        return sum;
    }
    // Driven Program
    let mat = [[112, 42, 83, 119],
           [56, 125, 56, 49],
           [15, 78, 101, 43],
           [62, 98, 114, 108]];
    document.write(maxSum(mat));
     
    // This code is contributed by avanitrachhadiya2155
</script>

414

Complejidad Temporal: O(N ² ).

Este artículo es una contribución de Anuj Chauhan . 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.