Verilen 2N X 2N matrisinden N X N üst sol alt matrisinin toplamını maksimuma çıkar
Verilen bir 2N x 2N tam sayıların matrisi. Herhangi bir satırı veya sütunu istediğiniz sayıda ve istediğiniz sırayla tersine çevirmenize izin verilir. Görev, sol üstteki değerlerin maksimum toplamını hesaplamaktır. N X N alt matris, yani (0 0)'dan (N - 1 N - 1)'e kadar alt matrisin elemanlarının toplamı.
Örnekler:
Giriş: ile[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
Çıkış : 414
Verilen matris 4 X 4 boyutundadır, maksimize etmemiz gerekir
sol üstteki 2 X 2 matrisinin toplamı yani
mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1] toplamı.
Aşağıdaki işlemler toplamı maksimuma çıkarır:
1. 2. sütunu ters çevirin
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2. 0. satırı ters çevirin
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
Sol üst matrisin toplamı = 119 + 114 + 56 + 125 = 414.
Sol üst alt matrisin toplamını en üst düzeye çıkarmak için, sol üst alt matrisin her hücresi için dört aday gözlemleyin; bu, sol üst-sağ üst-sol alt matrislerde ve sağ alt alt matrislerde değiştirilebilecek karşılık gelen hücreler anlamına gelir.
Şimdi, nerede olursa olsun her hücreyi gözlemleyin, sol üst alt matristeki diğer hücrelerin sırasını değiştirmeden, onu sol üst alt matristeki karşılık gelen aday değerle değiştirebiliriz. Diyagram, 4 adayın maksimum değerinin sağ üst alt matriste olduğu bir örneği göstermektedir. Sol alt veya sağ alt alt matrislerdeyse, önce bir satırı veya sütunu ters çevirerek sağ üst alt matrise yerleştirebiliriz ve ardından şemada gösterildiği gibi aynı işlem sırasını takip edebiliriz.
Bu matriste diyelim ki 26 en fazla 4 aday ve bir 23 ile değiştirilmelidir 26 sol üst alt matristeki hücrelerin sırasını değiştirmeden.
2. Sırayı Ters Çevir
Ters Sütun 2
7. Sırayı Ters Çevir
Sütun 6'yı Ters Çevir
2. Sırayı Ters Çevir
Aşağıda bu yaklaşımın uygulanması yer almaktadır:
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>
Çıkış
414
Zaman Karmaşıklığı: O(N) 2 ).
Yardımcı Alan: O(1) değişkenler için sabit alan kullandığından
Test Oluştur
