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

求最大子矩阵

题目描述

给定一个n*m的矩阵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。

题目分析

算法设计

package com.bean.algorithmbasic;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.Scanner;public class MaxSubMatrix2 {
       public static int n, m;    public static long[][] map;    public static long result = Long.MIN_VALUE;    public static void main(String[] args) throws FileNotFoundException {        //程序开始执行时间        long startTime=System.currentTimeMillis();        //设置数据来源文件        System.setIn(new FileInputStream("G:\\matrixnumber.txt"));        Scanner sc = new Scanner(System.in);        //读取行        n = sc.nextInt();        //读取列        m = sc.nextInt();        //声明一个二维数组        map = new long[n][m];        //初始化二维数组元素        for (int i = 0; i < n; i++)            for (int j = 0; j < m; j++)                //从文件中读取数据                map[i][j] = sc.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);        //程序执行结束时间        long endTime=System.currentTimeMillis();        System.out.println("程序执行时间: "+(endTime-startTime)+" ms");    }}

（完）

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