一个M*N的矩阵，找到此矩阵的一个子矩阵，并且这个子矩阵的元素的和是最大的，输出这个最大的值。
例如：3*3的矩阵：
-1 3 -1
2 -1 3
-3 1 2
和最大的子矩阵是：
3 -1
-1 3
1 2
收起
输入
第1行：M和N，中间用空格隔开（2 <= M,N <= 500)。 第2 - N + 1行：矩阵中的元素，每行M个数，中间用空格隔开。(-10^9 <= M[i] <= 10^9)
输出
输出和的最大值。如果所有数都是负数，就输出0。
输入样例
3 3 -1 3 -1 2 -1 3 -3 1 2
输出样例
7
分析：
我们首先确定我们求矩阵的上下两行i和j，这样求i行与j行之间的矩阵就变成了一个一维的最大字段和了，每一列当作一个数组元素，用前缀和的思想快速求出。
import java.util.Scanner;public class Main {static Long [][] a=new Long[505][505];static Long [][] sum=new Long[505][505];static Long [] dp=new Long[505];public static void main(String[] args) {Scanner in=new Scanner(System.in);int m=in.nextInt();int n=in.nextInt();sum[0]=new Long[505];for(int i=1;i<=n;i++){sum[i]=new Long[505];a[i]=new Long[505];for(int j=1;j<=m;j++){sum[0][j]=(long) 0;a[i][j]=in.nextLong();sum[i][j]=sum[i-1][j]+a[i][j];}}Long ans=(long) -1e18;for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){dp[0]=(long) 0;for(int k=1;k<=m;k++){dp[k]=Math.max(dp[k-1]+sum[j][k]-sum[i-1][k],sum[j][k]-sum[i-1][k]);ans=Math.max(dp[k],ans);}}if(ans<0) ans=(long) 0;System.out.println(ans);System.gc();}}