100m的网站 数据库,wordpress博客怎么访问不了,联网站,网站上传小马后怎么做元素和最大的子矩阵
题目描述
输入一个n级方阵#xff0c;请找到此矩阵的一个子矩阵#xff0c;此子矩阵的各个元素的和是所有子矩阵中最大的#xff0c;输出这个子矩阵及这个最大的和。
关于输入
首先输入方阵的级数n#xff0c; 然后输入方阵中各个元素。
关于输出 …元素和最大的子矩阵
题目描述
输入一个n级方阵请找到此矩阵的一个子矩阵此子矩阵的各个元素的和是所有子矩阵中最大的输出这个子矩阵及这个最大的和。
关于输入
首先输入方阵的级数n 然后输入方阵中各个元素。
关于输出
输出子矩阵 最后一行输出这个子矩阵的元素的和。
例子输入
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
例子输出
9 2
-4 1
-1 8
15
解题分析
这个程序是一个求解最大子矩阵和的问题。可以使用动态规划和Kadane算法。这个问题可以描述为给定一个二维数组找出其中的一个子矩阵使得这个子矩阵中所有元素的和最大。
这个程序的主要思路如下
1. 读取一个整数n然后读取一个nxn的整数矩阵a。
2. 计算total数组total[i][j]表示从a[0][j]到a[i][j]的元素之和。如果i为0total[i][j]就等于a[i][j]否则total[i][j]就等于total[i-1][j]a[i][j]。
3. 遍历所有可能的子矩阵。对于每一个子矩阵计算其元素之和然后与当前最大的子矩阵和进行比较。如果新的子矩阵和更大就更新最大的子矩阵和以及对应的子矩阵的左上角和右下角的坐标。
4. 在计算子矩阵和的过程中使用了Kadane算法。Kadane算法可以在O(n)的时间复杂度内求解最大子数组和的问题。在这个程序中Kadane算法被用来求解每一行元素之和的最大值。
5. 最后打印出最大子矩阵和以及对应的子矩阵的元素。
Kadane算法是一个用于解决最大子数组和问题的动态规划算法。最大子数组和问题可以描述为在一个一维数组中找出一个连续的子数组使得这个子数组中所有元素的和最大。
Kadane算法的基本思想是对于数组中的每个位置计算以该位置为结束点的所有子数组中和最大的那个子数组的和。然后从这些和中找出最大的那个就是最大子数组和。
具体来说算法的步骤如下
1. 初始化两个变量max_so_far和max_ending_here都设为数组的第一个元素。max_so_far表示到目前为止找到的最大子数组和max_ending_here表示以当前位置为结束点的子数组的最大和。
2. 对于数组中的每个位置首先计算max_ending_here array[i]然后与array[i]比较取较大的那个作为新的max_ending_here。这一步表示如果加上当前元素能使子数组和更大就加上当前元素否则就从当前元素开始新的子数组。
3. 然后比较max_so_far和max_ending_here取较大的那个作为新的max_so_far。这一步表示如果max_ending_here比max_so_far大就更新max_so_far。
4. 重复上述步骤直到遍历完数组。
5. 最后max_so_far就是最大子数组和。
Kadane算法的时间复杂度是O(n)因为它只需要遍历一次数组。这使得它在处理大规模数据时非常高效。
举个例子
让我们通过一些具体的例子来理解Kadane算法。
假设我们有一个数组{-2, -3, 4, -1, -2, 1, 5, -3}我们想找到这个数组中和最大的子数组。
我们可以按照Kadane算法的步骤来操作
1. 初始化max_so_far和max_ending_here为数组的第一个元素-2。
2. 对于数组中的第二个元素-3我们先计算max_ending_here array[i]得到-2 - 3 -5然后与-3比较取较大的那个作为新的max_ending_here所以max_ending_here更新为-3。然后比较max_so_far和max_ending_here取较大的那个作为新的max_so_far所以max_so_far保持不变还是-2。
3. 对于数组中的第三个元素4我们先计算max_ending_here array[i]得到-3 4 1然后与4比较取较大的那个作为新的max_ending_here所以max_ending_here更新为4。然后比较max_so_far和max_ending_here取较大的那个作为新的max_so_far所以max_so_far更新为4。
4. 以此类推我们可以得到以下的结果 i 3, array[i] -1, max_ending_here 3, max_so_far 4 i 4, array[i] -2, max_ending_here 1, max_so_far 4 i 5, array[i] 1, max_ending_here 2, max_so_far 4 i 6, array[i] 5, max_ending_here 7, max_so_far 7 i 7, array[i] -3, max_ending_here 4, max_so_far 7
5. 最后我们得到的max_so_far就是最大子数组和也就是7。这个最大和的子数组是{4, -1, -2, 1, 5}。
通过这个例子我们可以看到Kadane算法可以有效地找到最大子数组和而且只需要遍历一次数组。
代码实现
#include iostream
using namespace std;int a[1000][1000];
int total[1000][1000];
int result[1000];
int n;int getmax(int start,int end){int local_start0;int maxSumresult[0];int cur_maxresult[0];for(int i1;in;i){if(result[i]cur_maxresult[i]){cur_maxresult[i];local_starti;}else{cur_maxresult[i];}if(cur_maxmaxSum){startlocal_start;endi;maxSumcur_max;}}return maxSum;
}int main() {cinn;for(int i0;in;i)for(int j0;jn;j){cina[i][j];}for(int i0;in;i)for(int j0;jn;j){if(i0) total[i][j]a[i][j];else total[i][j]total[i-1][j]a[i][j];}int top0,bottom0,left0,right0;int maxSumtotal[0][0];for(int i0;in;i)for(int ji;jn;j){int start0,end0;for(int k0;kn;k){if(i0){result[k]total[j][k];}else{result[k]total[j][k]-total[i-1][k];}}int sumgetmax(start,end);if(summaxSum){maxSumsum;topi; bottomj; leftstart; rightend;}}for(int itop;ibottom;i)for(int jleft;jright;j){couta[i][j];if(j!right) cout ;else coutendl;}coutmaxSumendl;return 0;
}
