Maksimizēt N X N augšējās kreisās apakšmatricas summu no dotās 2N X 2N matricas
Ņemot vērā a 2N x 2N veselu skaitļu matrica. Jums ir atļauts apgriezt jebkuru rindu vai kolonnu neierobežotu skaitu reižu un jebkurā secībā. Uzdevums ir aprēķināt augšējās kreisās puses maksimālo summu N x N apakšmatrica, t.i., apakšmatricas elementu summa no (0 0) līdz (N - 1 N - 1).
Piemēri:
Ievade: ar[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Izvade: 414
Dotās matricas izmērs ir 4 x 4, kas mums ir jāpalielina
augšējās kreisās 2 X 2 matricas summa, t.i
mats[0][0] + mats[0][1] + mats[1][0] + mats[1][1].
Sekojošās darbības palielina summu:
1. Apgrieziet 2. kolonnu otrādi
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. Apgrieztā 0. rinda
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Kreisās augšējās matricas summa = 119 + 114 + 56 + 125 = 414.
Lai maksimāli palielinātu augšējās kreisās apakšmatricas summu, katrai augšējās kreisās apakšmatricas šūnai ir četri kandidāti, kas nozīmē atbilstošās šūnas augšējā kreisajā augšējā labajā apakšējā-kreisajā un apakšējā labajā apakšmatricā, ar kurām to var apmainīt.
Tagad novērojiet katru šūnu neatkarīgi no tā, kur tā atrodas, mēs varam to apmainīt ar atbilstošo kandidāta vērtību augšējā kreisajā apakšmatricā, nemainot citu šūnu secību augšējā kreisajā apakšmatricā. Diagramma parāda gadījumu, kad 4 kandidātu maksimālā vērtība ir augšējā labajā apakšmatricā. Ja tas atrodas apakšējā kreisajā vai apakšējā labajā apakšmatricā, mēs vispirms varam apgriezt rindu vai kolonnu, lai ievietotu to augšējā labajā apakšmatricā, un pēc tam sekot tādai pašai darbību secībai, kā parādīts diagrammā.
Šajā matricā teiksim a 26 ir maksimālais no 4 kandidātiem un a 23 jāmaina ar a 26 nemainot šūnu secību augšējā kreisajā apakšmatricā.
Apgrieztā rinda 2
Reversā 2. kolonna
Apgrieztā rinda 7
Reversā 6. sleja
Apgrieztā rinda 2
Tālāk ir sniegta informācija par šīs pieejas īstenošanu.
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>
Izvade
414
Laika sarežģītība: O(N 2 ).
Palīgtelpa: O(1) jo tas izmanto nemainīgu vietu mainīgajiem
Izveidojiet viktorīnu
