本文共 1155 字，大约阅读时间需要 3 分钟。

#include <cstdlib>#include <iostream>using namespace std;const int MAX = 101;int value[MAX][MAX] = {​{0,0}};int subMaxSum(int a[], int n){ int sum = 0, b = 0; for(int i=0; i<n; i++) { if(b > 0) b += a[i]; else b = a[i]; if(b > sum) sum = b; } return sum;} int maxSum(int n){ int sum = 0, max = 0; for(int i=0; i<n; i++) { int b[MAX] = {0}; for(int j=i; j<n; j++) { for(int k=0; k<n; k++) b[k] += value[j][k]; sum = subMaxSum(b, n); if(sum > max) max = sum; } } return max; }int main(int argc, char *argv[]){ //freopen("input.txt", "rt", stdin); // freopen("output.txt", "wt", stdout); int n; cin >> n; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) cin >> value[i][j]; } cout << maxSum(n); return EXIT_SUCCESS;} 

根据最大子序列和的做法， 将矩阵转化为1维的序列， 从第一行开始， 将矩阵每一列的和都加起来， 放到数组b中,于是b[0]代表从第i行开始到第n行为止的第0列的和， 于是数组b的每个元素是每一列的和， 然后利用最大子序列和的解法求解数组b的最大子序列和， 就是矩阵的最大子序列和了...

转载地址：http://rdkqb.baihongyu.com/