题目描述

先看一个一维的 连续子数组的最大和

题目要求求解的二维矩阵的最大值，矩阵的大小不固定

1.然后在代码中利用了滚动数组，因为每一次只用到了前面一个数的结果,和一维数组的同理
2.时间复杂度时O(nnm),当n>m的时候可以选择将矩阵的行和列对换

代码

package week;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 最强对手矩阵 {

    /**
     * @param args
     * @throws IOException 
     */
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
    //这个题之前做过但是忘记了
        BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        String[] p=bufferedReader.readLine().split(" ");
        int n=Integer.parseInt(p[0]);
        int m=Integer.parseInt(p[1]);
        int a[][]=new int [n+1][m+1];
        for(int i=1;i<=n;i++){
            p=bufferedReader.readLine().split(" ");
            for(int j=1;j<=m;j++){
                a[i][j]=Integer.parseInt(p[j-1]);
                a[i][j]+=a[i-1][j];
                //预处理前缀和，得到的是每一列的前缀和
            }
        }
        int ma=0;
        for (int i = 1; i <=n; i++) {
            for(int j=i;j<=n;j++){
                int last=0;
                //最初值为0，表示没有任何的数据
                for(int k=1;k<=m;k++){
                    int w=a[j][k]-a[i-1][k];
                    last=Math.max(0, last)+w;
                    ma=Math.max(last, ma);
                }
            }
        }
        System.out.println(ma);
    }

}