Maximieren Sie die Summe von N x N der oberen linken Untermatrix aus der gegebenen 2N x 2N-Matrix
Gegeben a 2N x 2N Matrix aus ganzen Zahlen. Sie können jede Zeile oder Spalte beliebig oft und in beliebiger Reihenfolge umkehren. Die Aufgabe besteht darin, die maximale Summe der oberen linken zu berechnen N X N Submatrix, d. h. die Summe der Elemente der Submatrix von (0 0) bis (N - 1 N - 1).
Beispiele:
Eingabe: mit[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Ausgabe : 414
Die gegebene Matrix hat die Größe 4 x 4, die wir maximieren müssen
die Summe der oberen linken 2 x 2-Matrix, d. h
die Summe von mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1].
Folgende Operationen maximieren die Summe:
1. Kehren Sie die Spalte 2 um
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. Reihe 0 umdrehen
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Summe der oberen linken Matrix = 119 + 114 + 56 + 125 = 414.
Um die Summe der Submatrix oben links zu maximieren, beachten Sie, dass es für jede Zelle der Submatrix oben links vier Kandidaten gibt, d. h. die entsprechenden Zellen in den Submatrizen oben links, oben rechts, unten links und unten rechts, mit denen sie ausgetauscht werden kann.
Beachten Sie nun, dass wir jede Zelle, wo auch immer sie sich befindet, mit dem entsprechenden Kandidatenwert in der Submatrix oben links austauschen können, ohne die Reihenfolge der anderen Zellen in der Submatrix oben links zu ändern. Das Diagramm zeigt einen Fall, in dem sich der Maximalwert der 4 Kandidaten in der Submatrix oben rechts befindet. Wenn es sich in den Untermatrizen unten links oder unten rechts befindet, können wir zunächst eine Zeile oder Spalte umkehren, um sie in die Untermatrix oben rechts einzufügen, und dann der gleichen Abfolge von Operationen folgen, wie im Diagramm gezeigt.
In dieser Matrix sagen wir a 26 ist das Maximum der 4 Kandidaten und a 23 muss mit a getauscht werden 26 ohne die Reihenfolge der Zellen in der Submatrix oben links zu ändern.
Reihe 2 umkehren
Spalte 2 umkehren
Reihe 7 umkehren
Spalte 6 umkehren
Reihe 2 umkehren
Nachfolgend finden Sie die Umsetzung dieses Ansatzes:
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>
Ausgabe
414
Zeitkomplexität: O(N 2 ).
Hilfsraum: O(1) da es konstanten Platz für Variablen verwendet
Quiz erstellen
