我要招人

去企业版

首页 > 试题广场 >

子矩阵的最大累加和问题

[编程题]子矩阵的最大累加和问题

热度指数：2597 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个矩阵matrix，其中的值有正、有负、有0，返回子矩阵的最大累加和

例如，矩阵matrix为：

-90 48 78

64 -40 64

-81 - 7 66

其中，最大的累加和的子矩阵为：

48 78

-40 64

-7 66

所以返回累加和209。

例如，matrix为：

-1 -1 -1

-1 2 2

-1 -1 -1

其中，最大累加和的子矩阵为：

2 2

所以返回4

[要求]

时间复杂度为

，空间复杂度为

输入描述:

第一行有两个整数N，M。分别表示矩阵的行数/列数
接下来N行，每行M个整数表示矩阵内的数

输出描述:

输出一个整数表示答案

示例1

输入

输出

示例2

输入

3 3
-1 -1 -1
-1 2 2
-1 -1 -1

输出

备注:

算法知识视频讲解

Java

pein531

用O(nm)的空间缓存列前缀和presum，presum[i]表示原始矩阵从第0行到第i行的累加和向量。要求任意子矩阵的累加和，我们只需要先求出presum[j]-presum[i]，即为原始矩阵第i+1行到第j行的累加和，划定好行的范围，然后在列的维度上求解一维数组的最大累加和就可以了。遍历所有的行范围，在列上求得的最大数组累加和中的最大值就是我们要的答案。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), m = Integer.parseInt(params[1]);
        int[][] arr = new int[n][m];
        for(int i = 0; i < n; i++){
            String[] line = br.readLine().split(" ");
            for(int j = 0; j < m; j++)
                arr[i][j] = Integer.parseInt(line[j]);
        }
        System.out.println(maxCumsum4Mat(arr));
    }
    
    private static int maxCumsum4Mat(int[][] presum) {
        int[] zeros = new int[presum[0].length];
        int maxSum = Integer.MIN_VALUE;
        // 先计算列上面的前缀和
        for(int i = 1; i < presum.length; i++){
            for(int j = 0; j < presum[0].length; j++)
                presum[i][j] += presum[i - 1][j];
        }
        for(int end = 0; end < presum.length; end++){
            if(end != 0){
                // 计算arr[start:end][:]上的最大子矩阵累加和
                for(int start = -1; start < end; start++)
                    maxSum = Math.max(maxSum, maxCumsum4Vec(arrSubtract(presum[end], start >= 0? presum[start]: zeros)));
            }else
                maxSum = Math.max(maxSum, maxCumsum4Vec(presum[end]));
        }
        return maxSum;
    }
    
    private static int maxCumsum4Vec(int[] arr) {
        int max = Integer.MIN_VALUE;
        int dp = arr[0];
        for(int i = 1; i < arr.length; i++){
            dp = dp > 0? dp + arr[i]: arr[i];     // 前面的贡献是正的就加上arr[i]，否则就从arr[i]重新开始算
            max = Math.max(max, dp);
        }
        return max;
    }
    
    private static int[] arrSubtract(int[] v1, int[] v2){
        for(int i = 0; i < v1.length; i++) v1[i] -= v2[i];
        return v1;
    }
}

发表于 2021-11-27 12:22:34 回复(0)

Java

叫我小du

import java.util.Scanner;

public class Main {
    private static int maxSubArraySum(int[] arr) {
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            sum += num;
            max = Math.max(max, sum);
            if (sum < 0) {
                sum = 0;
            }
        }
        return max;
    }

    private static int maxSubMatrixSum(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            int[] array = matrix[i];
            max = Math.max(max, maxSubArraySum(array));
            for (int k = 1; i + k < matrix.length; k++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    array[j] += matrix[i + k][j];
                }
                max = Math.max(max, maxSubArraySum(array));
            }
        }
        return max;
    }

    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 res = maxSubMatrixSum(matrix);
        System.out.println(res);
    }
}

发表于 2021-04-28 17:25:33 回复(0)

Java

苟或郭嘉生司懿

这道题和前一道数组求最大和子数组是一脉相承的，那道题是这道题的题母。这道题，先把不管1行，2行，3行，，，，，，的数组上下相加，变成一位数组，然后再套用那个模型。最后再比较几行的情况最好

import java.util.*;

public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n,m;
while(cin.hasNextInt())
{
n = cin.nextInt();
m=cin.nextInt();
int[][] a=new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
a[i][j]=cin.nextInt();
}
}

int res=findMaxSum(a);
System.out.println(res);

}
}

public static int findMaxSum(int[][] arr){

//起始行
int[] help;
int max=Integer.MIN_VALUE;
for(int i=0;i<arr.length;i++){
help=new int[arr[0].length];
//终止行
for(int j=i;j<arr.length;j++){

int res=0;
for(int k=0;k<help.length;k++){
help[k]=help[k]+arr[j][k];
res+=help[k];
if(res<0){
res=0;
}
max=Math.max(res,max);
}
}
}
return max;
}

}

发表于 2020-08-06 11:09:38 回复(0)

Java

Mono_Chrome

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();
            }
        }

        int[] s = null;
        int cur = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < matrix.length; i++) {
            s = new int[matrix[0].length];
            for (int j = i; j < matrix.length; j++) {
                cur = 0;
                for (int k = 0; k < matrix[0].length; k++) {
                    s[k] += matrix[j][k];
                    cur += s[k];
                    max = Math.max(max, cur);
                    if (cur < 0) {
                        cur = 0;
                    }
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2019-10-11 18:59:09 回复(0)

提交观点

问题信息

动态规划

上传者：小小

难度：

4条回答 40收藏 4813浏览

通过挑战的用户

查看代码

小蔡先生a

2023-02-27 18:00:48
nemo123

2023-02-18 17:05:16
希望被offe...

2022-11-02 00:23:15
牛客26436...

2022-10-22 22:09:53
Jiff与我无缘

2022-10-14 17:23:40

子矩阵的最大累加和问题

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题