给定一个 n×m 的矩阵 A,求 A中的一个非空子矩阵,使这个子矩阵中的元素和最大。其中,A 的子矩阵指在 A中行和列均连续的一部分。
输入格式
输入的第一行包含两个整数 n,mn,m(1≤n,m≤50),分别表示矩阵 A 的行数和列数。
接下来 n 行,每行 m个整数,表示矩阵 Ai,j(−1000≤Ai,j≤1000)。
输出格式
输出一行,包含一个整数,表示 AA 中最大子矩阵的元素和。
样例输入
3 3 2 -4 1 -1 2 1 4 -2 2
样例输出
6
import java.util.Scanner; public class Main { public static int n, m; public static long[][] map; public static long result = Long.MIN_VALUE; public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); map = new long[n][m]; for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) map[i][j] = in.nextLong(); for(int start = 0;start < n;start++) { //开始行 long[] ring = new long[m]; long[] dp = new long[m]; for(int end = start;end < n;end++) { //结束行 for(int j = 0;j < m;j++) //计算start~end行的每一列元素和 ring[j] += map[end][j]; result = Math.max(result, ring[0]); dp[0] = ring[0]; for(int j = 1;j < m;j++) { if(dp[j - 1] < 0) dp[j] = ring[j]; else dp[j] = dp[j - 1] + ring[j]; result = Math.max(result, dp[j]); } } } System.out.println(result); } }