企业官网建设流程全解析

玉树wap网站建设,快速建设网站视频,创造自己的网站,知乎系统是wordpress(新卷,100分)- 最大矩阵和#xff08;Java JS Python C#xff09;题目描述给定一个二维整数矩阵#xff0c;要在这个矩阵中选出一个子矩阵#xff0c;使得这个子矩阵内所有的数字和尽量大#xff0c;我们把这个子矩阵称为和最大子矩阵#xff0c;子矩…(新卷,100分)- 最大矩阵和Java JS Python C题目描述给定一个二维整数矩阵要在这个矩阵中选出一个子矩阵使得这个子矩阵内所有的数字和尽量大我们把这个子矩阵称为和最大子矩阵子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。输入描述输入的第一行包含2个整数n, m(1 n, m 10)表示一个n行m列的矩阵下面有n行每行有m个整数同一行中每2个数字之间有1个空格最后一个数字后面没有空格所有的数字的在[-1000, 1000]之间。输出描述输出一行一个数字表示选出的和最大子矩阵内所有的数字和。用例输入3 4-3 5 -1 52 4 -2 4-1 3 -1 3输出20说明一个3*4的矩阵中后面3列的子矩阵求和加起来等于20和最大。题目分析看到这个题目标题我很容易就联想到了最大子数组和区别在于最大子数组和是一维的而最大子矩阵和是二维的。那么是不是有可能将最大子矩阵和的求解转成一维的呢下面是子矩阵可能存在的区域即一行子矩阵两行子矩阵三行子矩阵进一步简化可得下图即对求解下面每个区域的最大子矩阵此时因为子矩阵的行数已经确定因此我们可以将多行压缩为一行此时对于最大子矩阵和的求解就变为了最大子数组和的求解。而最大子数组和的求解的状态转移方程我们已经在前一小结总结出来了dp[i] max(dp[i-1], 0) nums[i]。还有一个难点就是二维数组压缩为一维数组的问题解决思路如下获取二维数组的行数rows、列数cols创建一个长度为cols的一维数组然后将二维数组双重for循环外层遍历cols内层遍历rows这样每次循环就可以得到二维数组一个列上的所有元素然后求和存入一维数组中实现如下function matrixZip(matrix) { let cols matrix[0].length; let rows matrix.length; let zip new Array(cols).fill(0); for (let c 0; c cols; c) { for (let r 0; r rows; r) { zip[c] matrix[r][c]; } } return zip; }JavaScript算法源码/* JavaScript Node ACM模式 控制台输入获取 */ const readline require(readline); const rl readline.createInterface({ input: process.stdin, output: process.stdout, }); let lines []; let n, m; rl.on(line, (line) { lines.push(line); // 输入第一行时提取出m、n if (lines.length 1) { [n, m] lines[0].split( ).map((ele) parseInt(ele)); } // 输入第一行后再输入n行时则开始启动算法程序 if (lines.length - 1 n) { // 干掉第一行输入即lines中存储的全是就是matrix要素 lines.shift(); // matrix是算法程序的入参二维数组 let matrix []; // 将多行输入的matrix要素提取出来存到二维数组中 lines.forEach((line) { matrix.push( line .split( ) .map((ele) parseInt(ele)) .slice(0, m) ); }); // 调用算法程序 console.log(maxSubMatrixSum(matrix)); // 将输入归0重新接收下一轮 lines.length 0; } }); function maxSubMatrixSum(matrix) { let dp []; for (let i 0; i matrix.length; i) { dp.push(maxSubArraySum(matrix[i])); for (let j i 1; j matrix.length; j) { dp.push(maxSubArraySum(matrixZip(matrix.slice(i, j 1)))); } } return dp.sort((a, b) b - a)[0]; } function maxSubArraySum(nums) { let dp new Array(nums.length); let result (dp[0] nums[0]); for (let i 1; i nums.length; i) { dp[i] Math.max(dp[i - 1], 0) nums[i]; result Math.max(result, dp[i]); } return result; } function matrixZip(matrix) { let cols matrix[0].length; let rows matrix.length; let zip new Array(cols).fill(0); for (let c 0; c cols; c) { for (let r 0; r rows; r) { zip[c] matrix[r][c]; } } return zip; }Java算法源码import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] matrix new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { matrix[i][j] sc.nextInt(); } } System.out.println(getResult(n, m, matrix)); } public static int getResult(int n, int m, int[][] matrix) { ArrayListInteger dp new ArrayList(); for (int i 0; i n; i) { dp.add(maxSubArraySum(matrix[i])); // 一行子矩阵最大和 for (int j i 1; j n; j) { dp.add(maxSubArraySum(matrixZip(Arrays.copyOfRange(matrix, i, j 1)))); // 多行子矩阵最大和 } } return dp.stream().max((a, b) - a - b).orElse(0); // 求出最大和 } // 最大子数组和求解 public static int maxSubArraySum(int[] nums) { int[] dp new int[nums.length]; int res dp[0] nums[0]; for (int i 1; i nums.length; i) { dp[i] Math.max(dp[i - 1], 0) nums[i]; res Math.max(res, dp[i]); } return res; } // 多行子矩阵压缩为一行子数组 public static int[] matrixZip(int[][] matrix) { int cols matrix[0].length; int rows matrix.length; int[] zip new int[cols]; for (int c 0; c cols; c) { for (int r 0; r rows; r) { zip[c] matrix[r][c]; } } return zip; } }Python算法源码# 输入获取 n, m map(int, input().split()) matrix [list(map(int, input().split())) for i in range(n)] # 最大子数组和求解 def maxSubArraySum(nums): dp [0 for i in range(len(nums))] res dp[0] nums[0] for i in range(1, len(nums)): dp[i] max(dp[i - 1], 0) nums[i] res max(res, dp[i]) return res # 将多行子矩阵压缩为一维数组 def matrixZip(matrix): cols len(matrix[0]) rows len(matrix) zip [0 for i in range(cols)] for c in range(cols): for r in range(rows): zip[c] matrix[r][c] return zip # 算法入口 def getResult(n, m, matrix): dp [] for i in range(n): dp.append(maxSubArraySum(matrix[i])) for j in range(i 1, n): dp.append(maxSubArraySum(matrixZip(matrix[i:j 1]))) dp.sort() return dp[-1] # 算法调用 print(getResult(n, m, matrix))C算法源码#include stdio.h #include stdlib.h #include limits.h #define MAX(a,b) ((a) (b) ? (a) : (b)) int getResult(int n, int m, int matrix[n][m]); int maxSubArraySum(int nums[], int nums_size); int* matrixZip(int rowFrom, int rowTo, int rows, int cols, int matrix[rows][cols]); int main() { int n, m; scanf(%d %d, n, m); int matrix[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { scanf(%d, matrix[i][j]); } } printf(%d\n, getResult(n, m, matrix)); return 0; } int getResult(int n, int m, int matrix[n][m]) { int ans INT_MIN; for(int i0; in; i) { ans MAX(ans, maxSubArraySum(matrix[i], m)); // 一行子矩阵最大和 for(int ji1; jn; j) { ans MAX(ans, maxSubArraySum(matrixZip(i, j, n, m, matrix), m)); // 多行子矩阵最大和 } } return ans; } // 最大子数组和求解 int maxSubArraySum(int nums[], int nums_size) { int dp[nums_size]; int res dp[0] nums[0]; for(int i1; inums_size; i) { dp[i] MAX(dp[i-1], 0) nums[i]; res MAX(res, dp[i]); } return res; } // 多行子矩阵压缩为一行子数组 int* matrixZip(int rowFrom, int rowTo, int rows, int cols, int matrix[rows][cols]) { int* zip (int*) calloc(cols, sizeof(int)); for(int c 0; c cols; c) { for(int r rowFrom; r rowTo; r) { zip[c] matrix[r][c]; } } return zip; }