本文主要是介绍UVa 108: Maximum Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题用暴力解法+动态规划。分析如下：
对于某个1*m的矩阵，即一个数列，求其maximal sub-rectangle，可以通过求最大长连续字串和来求得（这个用到了动态规划）。
那么对于n*m的矩阵，将每列的各个数字求和，将得到一个1*m的矩阵，用上文所说的方法求得的最大和即为该n*m矩阵的所有行数为n的子矩阵中的最大子矩阵和。
那么这道题，通过枚举所有行数为1、2、3.....N 的矩阵（暴力），分别用上述方法压缩矩阵求最大连续字串和，找出其中最大值，即为所求结果。
我的解题代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <algorithm>
using namespace std;int table[100][100];
int sum[100];
int N;int max_continuous_sum()
{int maxs=0,s=0;for(int i=0; i<N; i++){if(s>=0) s+=sum[i];else s=sum[i];maxs = maxs>s ? maxs : s;}return maxs;
}
int main()
{cin >> N;int maxsum=0;int tmp;for(int i=0这篇关于UVa 108: Maximum Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
