題目：有一個正整數(shù)和負(fù)整數(shù)組成的NxN矩陣，請編寫代碼找出元素總和最大的子矩陣。請嘗試使用一個高效算法。
給定一個int矩陣mat和矩陣的階數(shù)n，請返回元素總和最大的子矩陣的元素之和。保證元素絕對值小于等于100000，且矩陣階數(shù)小于等于200。

測試樣例：
[[1,2,-3],[3,4,-5],[-5,-6,-7]],3

返回：10

解析：首先求得當(dāng)前行的最大連續(xù)和，然后把后面的每一行加在當(dāng)前行后繼續(xù)求最大連續(xù)和，直到最后一行遍歷完為止。

import java.util.*;public class SubMatrix {//求解數(shù)組的最大連續(xù)和public static int getMax(int [] arr){int max=arr[0];int sum =arr[0];for(int i=1;i<arr.length;i++){sum=Math.max(arr[i],arr[i]+sum);max=Math.max(sum,max);}return max;}public int sumOfSubMatrix(int[][] mat, int n) {int max=Integer.MIN_VALUE;for(int i=0;i<n;i++){int [] temp =mat[i];//當(dāng)前行max=Math.max(max,getMax(temp));//當(dāng)前行的最大值for(int j=i+1;j<n;j++){//循環(huán)加上后面的每一行再判斷最大值for(int m=0;m<n;m++){temp[m]+=mat[j][m];}max=Math.max(max,getMax(temp));}}return max;} }

總結(jié)

以上是生活随笔為你收集整理的《程序员面试金典》最大和子矩阵的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。