网站seo是什么,网站后台制作视频教程,刚做还网站第一时间抓取,当下最火的购物app最大矩阵的和
真题目录: 点击去查看 E 卷 100分题型 题目描述
给定一个二维整数矩阵#xff0c;要在这个矩阵中选出一个子矩阵#xff0c;使得这个子矩阵内所有的数字和尽量大#xff0c;我们把这个子矩阵称为和最大子矩阵#xff0c;子矩阵的选取原则是原矩阵中一块相互…最大矩阵的和
真题目录: 点击去查看 E 卷 100分题型 题目描述
给定一个二维整数矩阵要在这个矩阵中选出一个子矩阵使得这个子矩阵内所有的数字和尽量大我们把这个子矩阵称为和最大子矩阵子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。
输入描述
输入的第一行包含2个整数n, m(1 n, m 10)表示一个n行m列的矩阵下面有n行每行有m个整数同一行中每2个数字之间有1个空格最后一个数字后面没有空格所有的数字的在[-1000, 1000]之间。
输出描述
输出一行一个数字表示选出的和最大子矩阵内所有的数字和。
用例1
输入
3 4
-3 5 -1 5
2 4 -2 4
-1 3 -1 3输出
20说明 一个3*4的矩阵中后面3列的子矩阵求和加起来等于20和最大。 题解
思路将二维的问题转换为一维的问题。
转换思路最终选择的矩阵行数肯定是[1, n]。枚举出选择任意行的情况。选择多行时将同一列进行相加变成一行。问题就变成了在一行中求最大连续子数组了。最大子数组的状态转移方程dp[i] max(dp[i-1], 0) nums[i]。记录每种情况下的连续子数组和最大值其中的最大值就是结果。
c
#include iostream
#include vector
#include climits
using namespace std;#define MAX(a, b) ((a) (b) ? (a) : (b))int getResult(int n, int m, vectorvectorint matrix);
int maxSubArraySum(vectorint nums);
vectorint matrixZip(int rowFrom, int rowTo, int cols, vectorvectorint matrix);int main() {int n, m;cin n m;vectorvectorint matrix(n, vectorint(m));for (int i 0; i n; i) {for (int j 0; j m; j) {cin matrix[i][j];}}cout getResult(n, m, matrix) endl;return 0;
}int getResult(int n, int m, vectorvectorint matrix) {int ans INT_MIN;for (int i 0; i n; i) {ans MAX(ans, maxSubArraySum(matrix[i])); // 单行最大子数组和for (int j i 1; j n; j) {vectorint compressed matrixZip(i, j, m, matrix);ans MAX(ans, maxSubArraySum(compressed)); // 多行子矩阵最大和}}return ans;
}int maxSubArraySum(vectorint nums) {int res nums[0];int dp nums[0];for (size_t i 1; i nums.size(); i) {dp MAX(dp, 0) nums[i];res MAX(res, dp);}return res;
}vectorint matrixZip(int rowFrom, int rowTo, int cols, vectorvectorint matrix) {vectorint zip(cols, 0);for (int c 0; c cols; c) {for (int r rowFrom; r rowTo; 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))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、nif (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;
}Go
package mainimport (bufiofmtmathosstrconvstrings
)// 获取最大子矩阵和
func getResult(n, m int, matrix [][]int) int {ans : math.MinInt32for i : 0; i n; i {ans max(ans, maxSubArraySum(matrix[i])) // 单行最大子数组和for j : i 1; j n; j {compressed : matrixZip(i, j, m, matrix)ans max(ans, maxSubArraySum(compressed)) // 多行子矩阵最大和}}return ans
}// 最大子数组和Kadanes Algorithm
func maxSubArraySum(nums []int) int {res, dp : nums[0], nums[0]for i : 1; i len(nums); i {dp max(dp, 0) nums[i]res max(res, dp)}return res
}// 多行子矩阵压缩为一行
func matrixZip(rowFrom, rowTo, cols int, matrix [][]int) []int {zip : make([]int, cols)for c : 0; c cols; c {for r : rowFrom; r rowTo; r {zip[c] matrix[r][c]}}return zip
}// 获取最大值
func max(a, b int) int {if a b {return a}return b
}func main() {// 读取输入scanner : bufio.NewScanner(os.Stdin)scanner.Scan()line : scanner.Text()parts : strings.Fields(line)n, _ : strconv.Atoi(parts[0])m, _ : strconv.Atoi(parts[1])// 读取矩阵matrix : make([][]int, n)for i : 0; i n; i {matrix[i] make([]int, m)scanner.Scan()rowValues : strings.Fields(scanner.Text())for j : 0; j m; j {matrix[i][j], _ strconv.Atoi(rowValues[j])}}// 计算结果并输出fmt.Println(getResult(n, m, matrix))
}
