给定一个 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 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 iEndStep 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 maxsum){ maxsum = sum; pos = &(arr[i][0]); } for (int j=1; j maxsum){ maxsum = sum; pos = &(arr[i][j]); } } } for (int i=0; i输出
如果我们运行上面的程序，那么它将生成以下输出
4 45 5
登录后复制
以上就是在C程序中打印给定大小的最大和正方形子矩阵的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583179.html
