Maximizați suma N X N sub-matricei din stânga sus din matricea dată 2N X 2N
Având în vedere a 2N x 2N matricea numerelor întregi. Aveți voie să inversați orice rând sau coloană de câte ori și în orice ordine. Sarcina este de a calcula suma maximă din stânga sus N X N submatrice, adică suma elementelor submatricei de la (0 0) la (N - 1 N - 1).
Exemple:
Intrare: cu[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Ieșire: 414
Având în vedere că matricea este de dimensiunea 4 X 4, trebuie să o maximizăm
suma matricei 2 X 2 din stânga sus, adică
suma mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1].
Următoarele operațiuni maximizează suma:
1. Inversați coloana 2
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. Inversați rândul 0
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Suma matricei din stânga sus = 119 + 114 + 56 + 125 = 414.
Pentru a maximiza suma submatricei din stânga sus, observați pentru fiecare celulă a submatricei din stânga sus, există patru candidați, adică celulele corespunzătoare din submatricele din stânga sus, din dreapta sus și din dreapta jos, cu care poate fi schimbată.
Acum, observați pentru fiecare celulă, oriunde se află, o putem schimba cu valoarea candidatului corespunzătoare din submatricea din stânga sus, fără a modifica ordinea celorlalte celule din submatricea din stânga sus. Diagrama arată pentru un exemplu în care valoarea maximă a celor 4 candidați este în submatricea din dreapta sus. Dacă se află în submatricele din stânga jos sau din dreapta jos, putem mai întâi să inversăm un rând sau o coloană pentru a o pune în submatricea din dreapta sus și apoi să urmam aceeași secvență de operații așa cum este prezentată în diagramă.
În această matrice să spunem a 26 este maximul dintre cei 4 candidați și a 23 trebuie schimbat cu a 26 fără a modifica ordinea celulelor din submatricea din stânga sus.
Inversați rândul 2
Inversați coloana 2
Inversați rândul 7
Inversați coloana 6
Inversați rândul 2
Mai jos este implementarea acestei abordări:
C++ // C++ program to find maximum value of top N/2 x N/2 // matrix using row and column reverse operations #include #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 // 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 # 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# // 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 ?>
JavaScript < 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>
Ieșire
414
Complexitatea timpului: O(N 2 ).
Spațiu auxiliar: O(1) deoarece folosește spațiu constant pentru variabile
Creați un test
