首页 > 代码库 > 【HDU 1081】To The Max(求子矩阵元素和)
【HDU 1081】To The Max(求子矩阵元素和)
题目应该很容易看懂,是为了求一个矩阵之内最大的一个子矩阵的和。
子矩阵的和表示的是该矩阵内所有元素的和。
方法引入:
首先当然十分容易的可以想到一维求子段的和。
假设数组为a[110];
int sum = 0, MAX = 0,n; for (int i = 0; i < n; i++) { if (sum < 0) sum = 0; sum += a[i]; if (sum>MAX) MAX = sum; }
其中a[i]表示的是你所要积的范围大小,因为是一维,所以我们要积的是每一个元素。并且采取的是横向遍历即可。
由此迁移到二维。
二维采取的也是相同的方法,依然要找出a[i],但是循环多了一些。
思路我稍微描述一下(估计会看不懂):对于二维,做过覆盖面积最大的同学都知道,我们采取的是先处理横向,再处理竖向。
我们此处采取的方法就是固定横向,这边横向我们叫之为子矩阵的宽,我们去伸缩子矩阵的长,从而得到在此宽下,最大的子矩阵和。
然后在增大宽,并且移动宽的位置去重复以上的步骤,最终得到最大的子矩阵的和。(不知道听得懂不)
看下代码:
for (int i = 1; i <= n;i++)//这个循环控制宽的起点,1,2,3,,, for (int j =i; j <= n; j++)//这个循环去控制宽的长度,1,2,3,,, { sum = 0; for (int k = 1; k <= n; k++)//再此基础上k来控制长,相当于将一维的横向处理放到行上来。想一下,是不是如此? { if (sum < 0) sum = 0; sum += map[k][j] - map[k][i - 1];//map[k][j]-map[k][i-1]这边处理就可以得到宽,并且起点是从i开始的一条j-i+1长度的宽。 if (sum>MAX) MAX = sum; } }
看一下完整代码:
#include<iostream> using namespace std; /* 通过暴力的方法。 计算子矩阵和的方法,将二维转化成一维。 如何得到第k行,i-j的和。然后累加按一维的方法求出最大值。 */ int map[110][110]; int main() { int n; while (cin >> n) { for (int i = 1; i <= n; i++) { map[i][0] = 0; for (int j = 1; j <= n; j++) { scanf("%d", &map[i][j]); map[i][j] += map[i][j - 1]; } } int sum = 0; int MAX = 0; for (int i = 1; i <= n;i++)//这个循环控制宽的起点,1,2,3,,, for (int j =i; j <= n; j++)//这个循环去控制宽的长度,1,2,3,,, { sum = 0; for (int k = 1; k <= n; k++)//再此基础上k来控制长,相当于将一维的横向处理放到行上来。想一下,是不是如此? { if (sum < 0) sum = 0; sum += map[k][j] - map[k][i - 1];//map[k][j]-map[k][i-1]这边处理就可以得到宽,并且起点是从i开始的一条j-i+1长度的宽。 if (sum>MAX) MAX = sum; } } cout << MAX << endl; } }
【HDU 1081】To The Max(求子矩阵元素和)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。