给定一个 nxn 的矩阵，找到一个 mxm 的子矩阵，其中 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 矩阵。这种方法很简单，但需要 o(n^2.m^2) 时间复杂度，因此我们尝试找到一种时间复杂度较小的方法。
算法startstep 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
endstep 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 5void 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 45 5
以上就是在c程序中打印给定大小的最大和正方形子矩阵的详细内容。