本文共 743 字，大约阅读时间需要 2 分钟。
题意：给定N*N的矩阵，求最大子矩阵和
算法：动态规划。枚举子矩阵a[i,j]，表示从第i行到第j行组成的矩阵，将其每列相加，即可转换为求一维数组的最大连续子段和问题。 设dp[k]表示以元素k结束的最大子段和，那么，dp[k]=max{dp[k-1]+a[k],a[k]}#include#include using namespace std;const int SIZE=110;int INF = -127 * SIZE * SIZE;int a[SIZE][SIZE];int main(){ int n; cin >> n; for (int i=1; i<=n; i++) { for (int j=1; j<=n; j++) { cin >> a[i][j]; } } int sum[SIZE][SIZE]; memset(sum,0,sizeof(sum)); int ans = INF ; for (int i=1; i<=n; i++) { for (int j=i; j<=n; j++) { int dp[SIZE] ; for (int k=1; k<=n; k++) { sum[i][k] += a[j][k]; // sum[i][k] = sum[i:j][k] (dp[k-1] > 0)? dp[k] = dp[k-1] + sum[i][k] : dp[k] = sum[i][k]; if (dp[k] > ans) { ans = dp[k]; } } } } cout << ans << endl;}
转载地址：http://hrlbb.baihongyu.com/