问题

给定一个nxm的矩阵a，求a中的一个非空子矩阵，使这个子矩阵中的元素和最大。 其中，a的子矩阵指在a中行和列均连续的一块。 输入格式 输入的第一行包含两个整数n, m，分别表示矩阵a的行数和列数。 接下来n行，每行m个整数，表示矩阵a。 输出格式 输出一行，包含一个整数，表示a中最大的子矩阵中的元素和。

样例输入

3 3  -1 -4 3  3 4 -1  -5 -2 8  

样例输出

10

样例说明

取最后一列，和为10。 数据规模和约定 对于50%的数据，1<=n, m<=50； 对于100%的数据，1<=n, m<=500，a中每个元素的绝对值不超过5000。

思路

这题我是用动态规划求解，如下图，假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，如下所示(ari表示a[r][i],假设数组下标从1开始)：

| a11 …… a1i ……a1j ……a1n |  | a21 …… a2i ……a2j ……a2n |  |  ......................|  | ...................... |  | ar1 …… ari ……arj ……arn |  |  ......................|  | ...................... |  | ak1 …… aki ……akj ……akn |  |  ......................|  | an1 …… ani ……anj ……ann |  

那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下： (ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)，那么从中我们就可以把一个求子矩阵 的问题转换成一个求最大子段和 的问题，从中求出解。那么问题又来了，什么是最大子段和？怎么求最大子段和？ 首先，我们看一个问题：

给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值 比如当（a1,a2,a3,a4,a4,a6）=(-1,11,-1,13,-5,-2)时，最大子段和就为23。

用动态算法求解:

**b[j]=max{a[i]+a[j]},1<=i<=j,且1<=j<=n,则所求的最大子段和为max b[j]，1<=j<=n。 由b[j]的定义可易知，当b[j-1]>0时b[j]=b[j-1]+a[j]，否则b[j]=a[j]。故b[j]的动态规划递归式为: b[j]=max(b[j-1]+a[j],a[j])，1<=j<=n。

最大子段和算法

int getmaxarray(int a[],int n){//求最大子段和      int max=a[0],temp=0;      for (int i=0;i<n;i++) {          if (temp>0) {              temp+=a[i];          }else {              temp=a[i];          }          max=max>temp?max:temp;      }      return  max;  }  

实现代码

#include "stdio.h"  #include<string.h>  int dp[100];  int getmaxarray(int a[],int n){//求最大子段和      int max=a[0],temp=0;      for (int i=0;i<n;i++) {          if (temp>0) {              temp+=a[i];          }else {              temp=a[i];          }          max=max>temp?max:temp;      }      return  max;  }  int main(){      int n,m;      scanf("%d%d",&n,&m);      int a[n][m];      for(int i=0;i<n;i++){          for (int j=0;j<m;j++) {              scanf("%d",&a[i][j]);          }      }      int res=a[0][0],tmp;      for (int i=0;i<n;i++) {          memset(dp, 0, sizeof(dp));//将dp数组置为0          for (int j = i; j < n; ++j) {              for (int k = 0; k < m; ++k) {                  dp[k] += a[j][k];              }              tmp = getmaxarray(dp, n);              res = res > tmp ? res : tmp;          }      }      printf("%dn", res);  } 

转自：https://www.cnblogs.com/BIGOcean/p/12746341.html