指定された 2N X 2N 行列からの N X N 左上の部分行列の合計を最大化します
与えられた 2N×2N 整数の行列。任意の行または列を、何度でも、任意の順序で反転することができます。タスクは、左上の合計の最大値を計算することです。 N×N 部分行列、つまり、(0 0) から (N - 1 N - 1) までの部分行列の要素の合計。
例:
入力: with[][] = {
112 42 83 119
56 125 56 49
15 78 101 43
62 98 114 108
}
出力: 414
行列のサイズが 4 X 4 であるとすると、最大化する必要があります
左上の 2 X 2 行列の合計、つまり
mat[0][0] + mat[0][1] + mat[1][0] + mat[1][1] の合計。
次の操作により合計が最大化されます。
1. カラム 2 を反転します。
112 42 114 119
56 125 101 49
15 78 56 43
62 98 83 108
2.行0を反転します
119 114 42 112
56 125 101 49
15 78 56 43
62 98 83 108
左上の行列の合計 = 119 + 114 + 56 + 125 = 414。
左上の部分行列の合計を最大化するには、左上の部分行列の各セルについて、交換できる左上、右上、左下、および右下の部分行列の対応するセルを意味する 4 つの候補があることを確認します。
ここで、各セルがどこにあっても、左上の部分行列内の他のセルの順序を変更せずに、左上の部分行列内の対応する候補値と入れ替えることができることに注目してください。図は、4 つの候補の最大値が右上の部分行列内にある例を示しています。それが左下または右下の部分行列にある場合は、まず行または列を反転して右上の部分行列に配置し、次に図に示すのと同じ操作シーケンスに従うことができます。
このマトリックスでは、 26 は 4 つの候補の最大値であり、 23 と交換する必要があります 26 左上の部分行列のセルの順序は変更しません。
行 2 を反転
列 2 を反転
反転列 7
逆列 6
行 2 を反転
以下はこのアプローチの実装です。
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>
出力
414
時間計算量: O(N 2 ）。
補助スペース: O(1) 変数に定数スペースを使用しているため
クイズの作成
