Cプログラムで指定されたサイズの最大和二乗部分行列を出力します。

NxNの行列が与えられた場合、行列MxMのすべての要素の加算が最大になるように、M<=NおよびM>=1であるMxMの部分行列を見つけます。行列NxNの入力には、ゼロ、正、および負の整数値を含めることができます。

例

Input:
   {{1, 1, 1, 1, 1},
   {2, 2, 2, 2, 2},
   {3, 3, 3, 3, 3},
   {4, 4, 4, 4, 4},
   {5, 5, 5, 5, 5} }
Output:
   4 4
   5 5

上記の問題は、行列NxN全体を取得し、可能なすべてのMxM行列を見つけてそれらの合計を見つけ、合計が最大のMxMの1つの行列を出力するという単純な解決策で解決できます。このアプローチは簡単ですが、O（N ^ 2.M ^ 2）の時間計算量が必要なため、時間計算量の少ない方法を見つけようとしています。

アルゴリズム

Start
Step 1 -> Declare Function void matrix(int arr[][size], int k)
   IF k>size
      Return
   Declare int array[size][size]
   Loop For int j=0 and j<size and j++
      Set sum=0
   Loop for int i=0 and i<k and i++
      Set sum=sum + arr[i][j]
   End
   Set array[0][j]=sum
   Loop For int i=1 and i<size-k+1 and i++
      Set sum=sum+(arr[i+k-1]][j]-arr[i-1][j]
      Set arrayi][j]=sum
   End
   Set int maxsum = INT_MIN and *pos = NULL
   Loop For int i=0 and i<size-k+1 and i++)
      Set int sum = 0
      Loop For int j = 0 and j<k and j++
         Set sum += array[i][j]
      End
      If sum > maxsum
         Set maxsum = sum
         Set pos = &(arr[i][0])
      End
      Loop For int j=1 and j<size-k+1 and j++
         Set sum += (array[i][j+k-1] - array[i][j-1])
         IF sum > maxsum
            Set maxsum = sum
            Set pos = &(arr[i][j])
         End
      End
   End
   Loop For int i=0 and i<k and i++
      Loop For int j=0 and j<k and j++
         Print *(pos + i*size + j)
      End
      Print \n
   End
Step 2 -> In main()
   Declare int array[size][size] = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}}
   Declare int k = 2
   Call matrix(array, k)
Stop

例

#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
   if (k > size) return;
      int array[size][size];
   for (int j=0; j<size; j++){
      int sum = 0;
      for (int i=0; i<k; i++)
         sum += arr[i][j];
         array[0][j] = sum;
      for (int i=1; i<size-k+1; i++){
         sum += (arr[i+k-1][j] - arr[i-1][j]);
         array[i][j] = sum;
      }
   }
   int maxsum = INT_MIN, *pos = NULL;
   for (int i=0; i<size-k+1; i++){
      int sum = 0;
      for (int j = 0; j<k; j++)
         sum += array[i][j];
      if (sum > maxsum){
         maxsum = sum;
         pos = &(arr[i][0]);
      }
      for (int j=1; j<size-k+1; j++){
         sum += (array[i][j+k-1] - array[i][j-1]);
         if (sum > maxsum){
            maxsum = sum;
            pos = &(arr[i][j]);
         }
      }
   }
   for (int i=0; i<k; i++){
      for (int j=0; j<k; j++)
         cout << *(pos + i*size + j) << " ";
      cout << endl;
   }
}
int main(){
   int array[size][size] = {
      {1, 1, 1, 1, 1},
      {2, 2, 2, 2, 2},
      {3, 3, 3, 3, 3},
      {4, 4, 4, 4, 4},
      {5, 5, 5, 5, 5},
   };
   int k = 2;
   matrix(array, k);
   return 0;
}

出力

上記のプログラムを実行すると、次の出力が生成されます

4 4
5 5