子矩阵的最大累加和

迈不过友情╰ 2022-05-29 01:11 196阅读 0赞

![Center][]

//子矩阵的最大累加和
    public class SubMatrixSum{
    	
    	 //找出最大的子矩阵
    	public static int GetSubMatrixSum(int[][]matrix)
    	{
          if(matrix==null||matrix.length==0||matrix[0].length==0)
          {
          	return 0;
          }
          int sum=Integer.MIN_VALUE;
          int cur=0;
          int[]s=null ;  //存储行累加的数组
          for(int i=0;i<matrix.length;i++)
           {
          	  s=new int[matrix[0].length]; //列的长度,存储行累加的结果
    
          	 for(int j=i;j<matrix.length;j++)
          	 {  
                 cur=0;
                for(int k=0;k!=s.length;k++)
                {
                	s[k]+=matrix[j][k];
                	cur+=s[k];
                	sum=Math.max(sum,cur);
                	cur=cur<0?0:cur;
                }
                
          	 }
          }
    
          return sum;
           
    	}
    	//打印矩阵
    	public static void PrintMatrix(int[][]matrix,int row,int colum)
    	{
    		int sum=0;
    		for(int i=0;i<=row;i++)
    		{
    			 for(int j=0;j<=colum;j++)
    			 {
    			 	System.out.print(matrix[i][j]+" ");
    			 	sum+=matrix[i][j];
    			 }
    			 System.out.println();
    		}
          // System.out.println(sum);
    	}
    
    	public static void main(String[]args)
    	{
    	    //System.out.println("Hello");
    	    int[][]matrix={
       {-90,48,78},
    	                   {64,-40,64},
    	                   {-81,-7,66}};
    	    int row=matrix.length-1;
    	    int colum=matrix[0].length-1;
            PrintMatrix(matrix,row,colum);
            System.out.println(GetSubMatrixSum(matrix));
    
    	}
    }

![Center 1][]

[Center]: /images/20220529/27036ff18553451e99ee2d44990fc76e.png
[Center 1]: /images/20220529/ef4808fc4c8e410b9363fc1b4d83968b.png