logo

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة

نظرا أ 2N x 2N مصفوفة الأعداد الصحيحة. يُسمح لك بعكس أي صف أو عمود لأي عدد من المرات وبأي ترتيب. المهمة هي حساب الحد الأقصى لمجموع الجزء العلوي الأيسر ن × ن المصفوفة الفرعية أي مجموع عناصر المصفوفة الفرعية من (0 0) إلى (N - 1 N - 1).

خوارزمية k-nn

أمثلة:  

مدخل : مع[][] = {



                    112 42 83 119

                    56 125 56 49

                    15 78 101 43

                    62 98 114 108

                  }

الإخراج : 414

نظرًا لأن حجم المصفوفة 4 × 4، فنحن بحاجة إلى تعظيمها 

مجموع المصفوفة العلوية اليسرى 2 × 2 أي 

مجموع حصيرة [0] [0] + حصيرة [0] [1] + حصيرة [1] [0] + حصيرة [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.

لتعظيم مجموع المصفوفة الفرعية العلوية اليسرى، لاحظ لكل خلية من المصفوفة الفرعية العلوية اليسرى أن هناك أربعة مرشحين يقصدون الخلايا المقابلة في المصفوفات الفرعية العلوية اليسرى واليمنى السفلية واليسارية السفلية اليمنى التي يمكن تبديلها بها. 

لاحظ الآن أنه يمكننا مبادلة كل خلية أينما كانت بالقيمة المرشحة المقابلة في المصفوفة الفرعية العلوية اليسرى دون تغيير ترتيب الخلايا الأخرى في المصفوفة الفرعية العلوية اليسرى. يظهر الرسم البياني لمثال حيث تكون القيمة القصوى للمرشحات الأربعة في المصفوفة الفرعية العلوية اليمنى. إذا كان في المصفوفة الفرعية السفلية اليسرى أو السفلية اليمنى، فيمكننا أولاً عكس صف أو عمود لوضعه في المصفوفة الفرعية العلوية اليمنى ثم اتباع نفس تسلسل العمليات كما هو موضح في الرسم البياني. 

في هذه المصفوفة دعنا نقول أ26هو الحد الأقصى للمرشحين 4 و23يجب استبدالها ب26دون تغيير ترتيب الخلايا في المصفوفة الفرعية العلوية اليسرى.

مصفوفة' title=

عكس الصف 2 
 

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة


العمود العكسي 2 
 

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة

تحويل من سلسلة إلى عدد صحيح جافا


عكس الصف 7 
 

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة


العمود العكسي 6 
 

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة


عكس الصف 2 
 

أحجام النص اللاتكس

قم بتعظيم مجموع المصفوفة الفرعية اليسرى العلوية N X N من مصفوفة 2N X 2N المعطاة

وفيما يلي تنفيذ هذا النهج: 

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(N2).
المساحة المساعدة: O(1) لأنه يستخدم مساحة ثابتة للمتغيرات

 

إنشاء اختبار