题目描述

给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为“和最大子矩阵”。子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。

输入描述

输入的第一行包含两个整数 n 和 m (1 <= n, m <= 10)，表示矩阵的行数和列数。接下来的 n 行，每行有 m 个整数，表示矩阵的元素。矩阵元素的值在 [-1000, 1000] 范围内。

输出描述

输出一个整数，表示选出的和最大子矩阵内所有数字的和。

解题思路

这是一个典型的二维最大子矩阵和问题，可以通过Kadane算法解决。

1. Kadane算法是解决一维最大子数组和问题的经典算法。首先我们可以将二维问题转化为多个一维问题。对于每一对列 left 和 right，我们可以将它们之间的所有行数据进行累加，形成一个新的数组。然后，我们在这个数组上应用Kadane算法，求出这段区间的最大子数组和。

2. 具体步骤：

   • 对于每对列 left 和 right，将这两列之间的所有行累加起来，形成一个新的一维数组 temp，这个数组的每个元素表示的是矩阵中从第 left 列到第 right 列之间的所有行的累加和。
   • 然后，使用Kadane算法找到这个一维数组 temp 的最大子数组和，更新全局最大值。
   • 重复这个过程，遍历所有的列组合，得到最终的最大子矩阵和。

时间复杂度：

• 假设矩阵的大小为 n x m，对于每一对列组合 (left 和 right)，我们需要遍历所有的行，因此时间复杂度是 O(n * m^2)。由于 n 和 m 的最大值为 10，所以这个算法的时间复杂度是可接受的。

代码实现

C++

#include <bits/stdc++.h>
using namespace std;

// Kadane算法，返回一维数组的最大子数组和
int kadane(const vector<int>& nums) {
    int max_so_far = nums[0]; // 全局最大子数组和
    int current_max = nums[0]; // 在当前位置结束的最大子数组和
    
    for (int i = 1; i < nums.size(); ++i) {
        current_max = max(nums[i], current_max + nums[i]);
        max_so_far = max(max_so_far, current_max);
    }
    
    return max_so_far;
}

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

    int max_sum = INT_MIN;  // 初始化最大和为最小值

    // 遍历所有列的组合
    for (int left = 0; left < m; ++left) {
        vector<int> temp(n, 0);  // 临时数组，用于存储每列累加的和
        
        for (int right = left; right < m; ++right) {
            // 更新临时数组
            for (int i = 0; i < n; ++i) {
                temp[i] += matrix[i][right];
            }
            
            // 应用Kadane算法，找出当前列范围内的最大子数组和
            int sum = kadane(temp);
            max_sum = max(max_sum, sum); // 更新最大和
        }
    }

    // 输出结果
    cout << max_sum << endl;

    return 0;
}

Python

# Kadane算法，返回一维数组的最大子数组和
def kadane(nums):
    max_so_far = nums[0]
    current_max = nums[0]
    
    for i in range(1, len(nums)):
        current_max = max(nums[i], current_max + nums[i])
        max_so_far = max(max_so_far, current_max)
    
    return max_so_far

def main():
    n, m = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(n)]
    
    max_sum = -float('inf')  # 初始化最大和为负无穷大

    # 遍历所有列的组合
    for left in range(m):
        temp = [0] * n  # 临时数组，用于存储每列累加的和
        
        for right in range(left, m):
            # 更新临时数组
            for i in range(n):
                temp[i] += matrix[i][right]
            
            # 应用Kadane算法，找出当前列范围内的最大子数组和
            sum = kadane(temp)
            max_sum = max(max_sum, sum)  # 更新最大和
    
    print(max_sum)

if __name__ == "__main__":
    main()

Java

import java.util.Scanner;

public class Main {
    
    // Kadane算法，返回一维数组的最大子数组和
    public static int kadane(int[] nums) {
        int maxSoFar = nums[0];
        int currentMax = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        
        return maxSoFar;
    }
    
    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();
            }
        }

        int maxSum = Integer.MIN_VALUE;  // 初始化最大和为最小值

        // 遍历所有列的组合
        for (int left = 0; left < m; left++) {
            int[] temp = new int[n];  // 临时数组，用于存储每列累加的和
            
            for (int right = left; right < m; right++) {
                // 更新临时数组
                for (int i = 0; i < n; i++) {
                    temp[i] += matrix[i][right];
                }
                
                // 应用Kadane算法，找出当前列范围内的最大子数组和
                int sum = kadane(temp);
                maxSum = Math.max(maxSum, sum);  // 更新最大和
            }
        }

        System.out.println(maxSum);
        sc.close();
    }
}

题目描述

给定一个二维整数矩阵，要在这个矩阵中选出一个子矩阵，使得这个子矩阵内所有的数字和尽量大，我们把这个子矩阵称为和最大子矩阵，子矩阵的选取原则是原矩阵中一块相互连续的矩形区域。

输入描述

输入的第一行包含 $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$ ，和最大。