最大矩阵的和

最大矩阵的和

真题目录: 点击去查看

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、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;
}

Go

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
)

// 获取最大子矩阵和
func getResult(n, m int, matrix [][]int) int {
	ans := math.MinInt32

	for 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))
}