הגדל את הסכום של N X N מטריצת המשנה השמאלית העליונה ממטריצת 2N X 2N נתונה
בהינתן א 2N x 2N מטריצה של מספרים שלמים. אתה רשאי להפוך כל שורה או עמודה בכל מספר פעמים ובכל סדר. המשימה היא לחשב את הסכום המקסימלי של הצד השמאלי העליון N X N תת-מטריקס כלומר סכום הרכיבים של תת-המטריקס מ-(0 0) עד (N - 1 N - 1).
דוגמאות:
קלט: עם[][] = {
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 המועמדים נמצא בתת-המטריצה הימנית העליונה. אם הוא נמצא בתת-המטריצה השמאלית התחתונה או הימנית התחתונה, נוכל תחילה להפוך שורה או עמודה כדי לשים אותה בתת-המטריצה הימנית העליונה ולאחר מכן לבצע את אותו רצף של פעולות כפי שמוצג בתרשים.
במטריצה זו נניח א 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) מכיוון שהוא משתמש במרחב קבוע למשתנים
צור חידון
