子矩阵最大累加和

题目描述

给定一个矩阵matrix，其中的值有正、有负、有0，返回子矩阵的最大累加和。
例如，matrix为
-1 -1 -1
-1 2 2
-1 -1 -1
其中最大累加和的子矩阵为：
2 2
所以返回4.

解题思路

拿前两行举个例子：第一列-1+(-1)=-2,它不可能在最大子矩阵中（反证法：假设它在最大子矩阵中，把它丢弃岂不是更大）。第2列-1+2=1，有可能是最大值，做个记录。第3列与第2列的累加和-1+2+(-1+2)=2，有可能是最大值，再做个记录。一行和三行的情况也是同理。

package com.company;

import com.company.util.MatrixUtil;

public class Test5 {
    public static void main(String[] args) {
        /*int[][] A={
                {-1,-1,-1},
                {-1,2,2},
                {-1,-1,-1}
        };*/

        int[][] A=MatrixUtil.randomMatrix(3,3,-10,10);

        int max=Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            for (int j = i; j < A.length; j++) {
                int num=matrix(A,i,j);
                max=num>max?num:max;
            }
        }
        MatrixUtil.printMatrix(A);
        System.out.println(max);
    }
    public static int matrix(int[][] A,int begin,int end){
        int sum=0;
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < A[0].length; i++) {//列
            for (int j = begin; j <=end; j++) {//行
                sum+=A[j][i];
            }
            //如果sum<0,sum重置为0
            if(sum<0)
                sum=0;
            else
                max=sum>max?sum:max;
            //否则，有可能是最大值
        }
        return max;
    }


}

package com.company.util;

import java.util.Random;

public class MatrixUtil {
    public static void main(String[] args) {
        int[][] matrix=randomMatrix(3,3,0,10);
        printMatrix(matrix);
    }
    public static int[][] randomMatrix(int row,int col,int min,int max){
        int[][] matrix=new int[row][col];
        for (int i = 0; i < row; i++) {
            matrix[i]=new int[col];
        }

        Random r=new Random();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int num=r.nextInt(max-min)+min;
                matrix[i][j]=num;
            }
        }

        return matrix;
    }
    public static void printMatrix(int[][] matrix){
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(j!=matrix[0].length-1)
                System.out.print(matrix[i][j]+",");
                else
                System.out.print(matrix[i][j]);
            }
            System.out.println();
        }
    }
}