Maksimaliai padidinkite N X N viršutinės kairiosios matricos sumą iš pateiktos 2N X 2N matricos
Atsižvelgiant į a 2N x 2N sveikųjų skaičių matrica. Galite apversti bet kurią eilutę ar stulpelį bet kokį skaičių kartų ir bet kokia tvarka. Užduotis yra apskaičiuoti didžiausią viršutinio kairiojo kampo sumą N X N submatrica, ty submatricos elementų suma nuo (0 0) iki (N - 1 N - 1).
Pavyzdžiai:
Įvestis: su[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Išvestis: 414
Pateikta matrica yra 4 x 4 dydžio, kurią turime padidinti
viršutinės kairiosios 2 X 2 matricos suma t.y
matas[0][0] + matas[0][1] + matas[1][0] + matas[1][1].
Šios operacijos padidina sumą:
1. Apverskite 2 stulpelį
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. Apverskite 0 eilutę
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Viršutinės kairiosios matricos suma = 119 + 114 + 56 + 125 = 414.
Norėdami maksimaliai padidinti viršutinės kairiosios submatricos sumą, stebėkite kiekvieną viršutinės kairiosios submatricos langelį, kad yra keturi kandidatai, reiškiantys atitinkamas ląsteles viršutiniame kairiajame viršutiniame dešiniajame apatiniame kairiajame ir apatiniame dešiniajame submatricose, su kuriomis ji gali būti pakeista.
Dabar stebėkite kiekvieną langelį, kad ir kur jis būtų, galime sukeisti jį atitinkama kandidato verte viršutinėje kairėje submatricoje, nekeisdami kitų langelių tvarkos viršutinėje kairėje submatricoje. Diagrama rodo atvejį, kai didžiausia 4 kandidatų vertė yra viršutinėje dešinėje submatricoje. Jei jis yra apatinėje kairėje arba apačioje dešinėje submatricose, pirmiausia galime apversti eilutę arba stulpelį, kad įdėtume ją į viršutinę dešinę pomatricą, o tada atlikite tą pačią operacijų seką, kaip parodyta diagramoje.
Šioje matricoje tarkime a 26 yra didžiausias iš 4 kandidatų ir a 23 turi būti pakeistas į a 26 nekeičiant langelių tvarkos viršutinėje kairėje submatricoje.
Atvirkštinė 2 eilutė
Atvirkštinis 2 stulpelis
Atvirkštinė 7 eilutė
Atvirkštinis 6 stulpelis
Atvirkštinė 2 eilutė
Žemiau pateikiamas šio metodo įgyvendinimas:
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>
Išvestis
414
Laiko sudėtingumas: O(N 2 ).
Pagalbinė erdvė: O(1) nes ji naudoja pastovią erdvę kintamiesiems
Sukurti viktoriną
