给定一个 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 maxsum Set maxsum = sum Set pos = &(arr[i][0]) End Loop For int j=1 and j 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 PrintEndStep 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 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 maxsum){ maxsum = sum; pos = &(arr[i][0]); } for (int j=1; j 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程序中打印给定大小的最大和正方形子矩阵的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444549.html
微信扫一扫 
支付宝扫一扫 
