בהינתן א 2N x 2N מטריצה של מספרים שלמים. אתה רשאי להפוך כל שורה או עמודה בכל מספר פעמים ובכל סדר. המשימה היא לחשב את הסכום המקסימלי של הצד השמאלי העליון N X N תת-מטריקס כלומר סכום הרכיבים של תת-המטריקס מ-(0 0) עד (N - 1 N - 1).
דוגמאות:
קלט: עם[][] = {
112 42 83 119
תו למחרוזת java56 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].
הפעולות הבאות ממקסמות את הסכום:
sql concat1. הפוך את העמודה 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 המועמדים נמצא בתת-המטריצה הימנית העליונה. אם הוא נמצא בתת-המטריצה השמאלית התחתונה או הימנית התחתונה, נוכל תחילה להפוך שורה או עמודה כדי לשים אותה בתת-המטריצה הימנית העליונה ולאחר מכן לבצע את אותו רצף של פעולות כפי שמוצג בתרשים.
ביטוי רגולרי ב-java
במטריצה זו נניח א26הוא המקסימום מבין 4 המועמדים וא23יש להחליף עם א26מבלי לשנות את סדר התאים בתת המטריצה השמאלית העליונה.
הפוך שורה 2
עמודה 2 הפוכה
הפוך שורה 7
עמודה 6 הפוכה
כיצד להמיר מחרוזת ל-int
הפוך שורה 2
להלן היישום של גישה זו:
C++// C++ program to find maximum value of top N/2 x N/2 // matrix using row and column reverse operations #include
// 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 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# 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 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 ?> <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(N2).
מרחב עזר: O(1) מכיוון שהוא משתמש במרחב קבוע למשתנים
צור חידון