Maximaliseer de som van de NX N-submatrix linksboven uit de gegeven 2N X 2N-matrix
Gegeven een 2N x 2N matrix van gehele getallen. U mag een rij of kolom een willekeurig aantal keren en in elke volgorde omkeren. De taak is om de maximale som van linksboven te berekenen N X N submatrix, d.w.z. de som van elementen van de submatrix van (0 0) tot (N - 1 N - 1).
Voorbeelden:
Invoer: met[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Uitgang: 414
Gegeven dat de matrix de grootte 4 X 4 heeft, moeten we maximaliseren
de som van de 2 X 2 matrix linksboven, d.w.z
de som van mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1].
De volgende bewerkingen maximaliseren de som:
1. Keer de kolom om 2
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. Rij 0 omkeren
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Som van matrix linksboven = 119 + 114 + 56 + 125 = 414.
Om de som van de submatrix linksboven te maximaliseren, observeert u voor elke cel van de submatrix linksboven vier kandidaten, dat wil zeggen de overeenkomstige cellen in de submatrices linksboven rechtsonder en rechtsonder waarmee deze kan worden verwisseld.
Kijk nu voor elke cel waar deze zich ook bevindt, we kunnen deze verwisselen met de overeenkomstige kandidaatwaarde in de submatrix linksboven zonder de volgorde van de andere cellen in de submatrix linksboven te veranderen. Het diagram toont voor een voorbeeld waarbij de maximale waarde van de 4 kandidaten zich in de submatrix rechtsboven bevindt. Als het zich in de submatrix linksonder of rechtsonder bevindt, kunnen we eerst een rij of kolom omkeren om deze in de submatrix rechtsboven te plaatsen en vervolgens dezelfde reeks bewerkingen volgen als weergegeven in het diagram.
Laten we in deze matrix a zeggen 26 is het maximum van de 4 kandidaten en a 23 moet worden verwisseld met een 26 zonder de volgorde van de cellen in de submatrix linksboven te veranderen.
Omgekeerde rij 2
Omgekeerde kolom 2
Omgekeerde rij 7
Omgekeerde kolom 6
Omgekeerde rij 2
Hieronder vindt u de implementatie van deze aanpak:
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>
Uitvoer
414
Tijdcomplexiteit: O(N 2 ).
Hulpruimte: O(1) omdat het constante ruimte gebruikt voor variabelen
Quiz maken
