小猿发现了一根侧面写着数字的圆柱,仔细观察发现柱子的侧面被分割成了N行M列的若干个小格子,每个格子里写着一个数字。 你能帮助小猿找到圆柱侧面的最大子矩阵吗?-笔试面试资料

这是qklbishe.com第14711 篇笔试面试资料
提供答案分析,通过本文《小猿发现了一根侧面写着数字的圆柱,仔细观察发现柱子的侧面被分割成了N行M列的若干个小格子,每个格子里写着一个数字。 你能帮助小猿找到圆柱侧面的最大子矩阵吗?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

小猿发现了一根侧面写着数字的圆柱,仔细观察发现柱子的侧面被分割成了N行M列的若干个小格子,每个格子里写着一个数字。
你能帮助小猿找到圆柱侧面的最大子矩阵吗?
小猿发现了一根侧面写着数字的圆柱,仔细观察发现柱子的侧面被分割成了N行M列的若干个小格子,每个格子里写着一个数字。    你能帮助小猿找到圆柱侧面的最大子矩阵吗? 零葬
其实就是二维数组版连续子数组最大和,利用动态规划求解。
(1)合并行和,构造一个辅助数组calSum,其中calSum[i][j]表示第j列前i行的元素之和;
(2)然后用两重循环遍历行范围的可能性,循环内部化简为一维数组版的连续子数组的最大和。
由于题中表示这个二维数组是个圆柱面,因此需要考虑环的问题。这里我们采用一个取巧的方式去避开环的情况,用动态规划求解连续列子数组的最大和和最小和,其中最大和是不考虑环的情况,用所有列的总和减去最小和就是考虑环时候的最大和,选择这两种情况大的那个即可。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException;  public class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String[] params = br.readLine().split(" ");         int m = Integer.parseInt(params[0]);         int n = Integer.parseInt(params[1]);         int[][] matrix = new int[n][n];         for(int i = 0; i < m; i++){             String[] row = br.readLine().split(" ");             for(int j = 0; j < n; j++)                 matrix[i][j] = Integer.parseInt(row[j]);         }         int[][] calSum = new int[m][n];     // calSum[i][j]表示前i行第j列的元素之和         for(int i = 0; i < m; i++){             for(int j = 0; j < n; j++)                 calSum[i][j] = (i != 0? calSum[i - 1][j]: 0) + matrix[i][j];         }         int maxSize = Integer.MIN_VALUE;         int[] colSum = new int[n];         for(int startRow = -1; startRow < m; startRow ++){             for(int endRow = startRow + 1; endRow < m; endRow ++){                 // 接下来与求数组的连续子数组最大和相同                 int sumBetweenStartrowAndEndrow = 0;                 int tempMaxSum = calSum[endRow][0] - (startRow == -1? 0: calSum[startRow][0]);                 int tempMinSum = tempMaxSum;                 for(int col = 0; col < n; col++)                     sumBetweenStartrowAndEndrow += calSum[endRow][col] - (startRow == -1? 0: calSum[startRow][col]);                 for(int col = 1; col < n; col ++){                     // startRow=-1需要求取第一行在第col列的和,由于第一行没有前缀和做差,所以需要特殊处理                     colSum[col] = startRow == -1? calSum[endRow][col]: calSum[endRow][col] - calSum[startRow][col];                     tempMaxSum = Math.max(colSum[col], colSum[col] + tempMaxSum);                     tempMinSum = Math.min(colSum[col], colSum[col] + tempMinSum);                     maxSize = Math.max(sumBetweenStartrowAndEndrow - tempMinSum, Math.max(maxSize, tempMaxSum));                 }             }         }         System.out.println(maxSize);     } }

今天 18:42:03 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 小猿发现了一根侧面写着数字的圆柱,仔细观察发现柱子的侧面被分割成了N行M列的若干个小格子,每个格子里写着一个数字。 你能帮助小猿找到圆柱侧面的最大子矩阵吗?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情