UVA - 108 Maximum Sum

本文主要是介绍UVA - 108 Maximum Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：求最小的子矩阵和，是uva 507 的一个加深吧，从一维变成了二微，那么我们就转化为一维的，每一列的数，可以组成连续的子序列，然后将这个子序列当成一个元素，其它列同样如此，就可以转化为一维的了

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 123;int a[MAXN][MAXN],b[MAXN],n,sum,Max;int main()
{scanf("%d",&n);Max = -123456;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)scanf("%d",&a[i][j]);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)  //存着这一列的和b[j] = 0;for (int j = i; j < n; j++){sum = 0;for (int l = 0; l < n; l++){b[l] += a[j][l];if (sum >= 0)sum += b[l];else sum = b[l]; //找到了这次序列的最大值了if (sum > Max)Max = sum;}}}printf("%d\n",Max);return 0;
}

这篇关于UVA - 108 Maximum Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---