最大矩阵的和

最大矩阵的和

真题目录: 点击去查看

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, vector<vector<int>>& matrix);
int maxSubArraySum(vector<int>& nums);
vector<int> matrixZip(int rowFrom, int rowTo, int cols, vector<vector<int>>& matrix);int main() {int n, m;cin >> n >> m;vector<vector<int>> matrix(n, vector<int>(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, vector<vector<int>>& 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++) {vector<int> compressed = matrixZip(i, j, m, matrix);ans = MAX(ans, maxSubArraySum(compressed)); // 多行子矩阵最大和}}return ans;
}int maxSubArraySum(vector<int>& 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;
}vector<int> matrixZip(int rowFrom, int rowTo, int cols, vector<vector<int>>& matrix) {vector<int> 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) {ArrayList<Integer> 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 ("bufio""fmt""math""os""strconv""strings"
)// 获取最大子矩阵和
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
}// 最大子数组和（Kadane's 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))
}