首页 > 试题广场 >

以下函数用于找到整数矩阵matrix中，元素之和最大的n行m

[问答题]

以下函数用于找到整数矩阵matrix中，元素之和最大的n行m列的子矩阵的元素之和。请指出程序代码中错误的地方（问题不止一处，请尽量找出所有你认为错误的地方），并在不新增代码行的情况下将问题修复。

1 int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
2                     int n, int m) {
3   int base_sum;
4   for (int i = 0; i < n; i++){
5     for (int j = 0; j < m; j++){
6       base_sum += matrix[i][j];
7     }
8   }
9   int result = 0;
10   for (int i = 0; i + n < matrix.size(); i++) {
11     if(i > 0){
12       for (int y = 0; y < m; y++){
13         base_sum += matrix[i + n][y] - matrix[i - 1][y];
14       }
15     }
16     int real_sum = base_sum;
17     if (real_sum > result) {
18       result = real_sum;
19     }
20     for (int j = 0; j + m < matrix.size(); j++) {
21       for (int x = 0; x < n; x++) {
22         real_sum += matrix[x][j + m] - matrix[x][j - 1];
23       }
24       if (real_sum > result) {
25         result = real_sum;
26       }
27     }
28   }
29   return result;
30 }

hliang

1 int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
2                     int n, int m) {
3   int base_sum;
4   for (int i = 0; i < n; i++){
5     for (int j = 0; j < m; j++){
6       base_sum += matrix[i][j];
7     }
8   }
9   int result = 0;
10   for (int i = 0; i + n < matrix.size(); i++) {
11     if(i > 0){
12       for (int y = 0; y < m; y++){
13         base_sum += matrix[i + n-1][y] - matrix[i - 1][y];
14       }
15     }
16     int real_sum = base_sum;
17     if (real_sum > result) {
18       result = real_sum;
19     }
20     for (int j = 0; j + m < matrix[0].size(); j++) {
21       for (int x = i; x < i+n; x++) {
22         real_sum += matrix[x][j + m] - matrix[x][j];
23       }
24       if (real_sum > result) {
25         result = real_sum;
26       }
27     }
28   }
29   return result;
30 }

发表于 2018-12-09 13:25:31 回复(0)

Schrodingers_Cat

主要问题在于边界处理不合适

1. 行的上界为i + n - 1而不是i + n

2. 列的上界为j + m - 1而不是j + m

3. 对最后对行进行求和的时候元素的行索引是i + x 而不是x

int maxSubmatrixSum(std::vector<std::vector<int>> matrix, int n, int m){

int base_sum;

for (int i = 0; i < n; i++){

for (int j = 0; j < m; j++){

base_sum += matrix[i][j];

}

int result = 0;

for (int i = 0; i + n - 1 < matrix.size(); i++) {

if(i > 0){

for (int y = 0; y < m; y++){

base_sum += matrix[i + n - 1][y] - matrix[i - 1][y];

}

int real_sum = base_sum;

if (real_sum > result) {

result = real_sum;

}

for (int j = 0; j + m - 1 < matrix.size(); j++) {

for (int x = 0; x < n; x++) {

real_sum += matrix[i+x][j + m - 1] - matrix[i+x][j - 1];

}

if (real_sum > result) {

result = real_sum;

}

return result;

}

发表于 2019-03-15 20:52:06 回复(0)

(ง•̀_•́)ง😀️

主要问题在于：
第10行循环结束的条件应为i+n-1<matrix.size();
第13行 base_sum += matrix[i + n-1][y] - matrix[i - 1][y];
第21行 x从i开始，到x<i+n
第22行 real_sum += matrix[x][j + m] - matrix[x][j];

 1 int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
 2                     int n, int m) {
 3   int base_sum;
 4   for (int i = 0; i < n; i++){
 5     for (int j = 0; j < m; j++){
 6       base_sum += matrix[i][j];
 7     }
 8   }
 9   int result = 0;
10   for (int i = 0; i + n-1 < matrix.size(); i++) {
11     if(i  > 0){
12       for (int y = 0; y < m; y++){
13         base_sum += matrix[i + n-1][y] - matrix[i - 1][y];
14       }
15     }
16     int real_sum = base_sum;
17     if (real_sum  > result) {
18       result = real_sum;
19     }
20     for (int j = 0; j + m < matrix[i].size(); j++) {
21       for (int x = i; x < i+n; x++) {
22         real_sum += matrix[x][j + m] - matrix[x][j];
23       }
24       if (real_sum > result) {
25         result = real_sum;
26       }
27     }
28   }
29   return result;
30 }

编辑于 2019-06-14 09:54:02 回复(0)

牛客676898965号

#include <iostream>
#include <vector>

int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
    int n, int m)
{
    int base_sum=0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            base_sum += matrix[i][j];

        }

    }
    int result = 0;
    for (int i = 0; i + n < matrix.size(); i++)
    {
        if (i > 0)
        {
            for (int y = 0; y < m; y++)
            {
                base_sum += matrix[i + n-1][y] - matrix[i - 1][y];

            }

        }
        int real_sum = base_sum;
        if (real_sum > result)
        {
            result = real_sum;

        }
        for (int j = 1; j + m < matrix[0].size(); j++)
        {
            for (int x = i; x < matrix.size(); x++)
            {
                real_sum += matrix[x][j + m-1] - matrix[x][j - 1];

            }
            if (real_sum > result) {
                result = real_sum;

            }

        }

    }
    return result;

}

发表于 2020-08-23 00:02:11 回复(0)

OTGOTG

- 应对 n、m做检查，确保 n>=0 && n<=matrix.size(), m>=0 && m<=matrix[0].size();

- for (int j = 0; j + m < matrix.size(); j++) {、 for (int i = 0; i + n < matrix.size(); i++) { 的i、j 应该用long long类型，因为这个matrix可能会非常大

- base_sum, result, real_sum 都应该是long long

- result应初始化为 (1<<63) (64位机器上，long long 的最小值)

发表于 2019-09-07 21:13:25 回复(0)

吴盼盼小童鞋

int maxSubmatrixSum(std::vector<std::vector<int>> matrix,int n,int m){
    int base_sum = 0;
    for(int i=0 ; i<n ; i++){
        for(int j=0 ; j<m ; j++){
            base_sum += matrix[i][j];
        }
    }
    
    int result = 0;
    for(int i=0 ; i+n<matrix.size() ; i++){
        if(i>0){
            for(int y=0 ; y<m ; y++){
                result += matrix[i+n][y] - matrix[i-1][y]; 
            }
        }
        int real_sum = base_sum;
        if(real_sum > result){
            result = real_sum;
        }
        for(int j=0 ; j+m<matrix.size() ; j++){
            for(int x=0 ; x<n ; x++){
                real_sum += matrix[x][j+m] - matrix[x][j-1];
            }    
            if(real_sum>result){
                result = real_sum;
            }
        }
    }
    return result;
}

发表于 2019-05-03 18:50:48 回复(0)

牛克李

int maxSubmatrixSum(std::vector<std::vector<int>> matrix,int n, int m) {     int base_sum=0;    /*初始化***/     for (int i = 0; i < n; i++) {         for (int j = 0; j < m; j++) {             base_sum += matrix[i][j];         }     }     int result = 0;     for (int i = 0; i + n <= matrix.size(); i++) {      /*  <=  */         if (i > 0) {             for (int y = 0; y < m; y++) {                 base_sum += matrix[i + n-1][y] - matrix[i - 1][y];    /*  -1  */             }         }         int real_sum = base_sum;         if (real_sum > result) {             result = real_sum;         }         for (int j = 1; j + m <= matrix[0].size(); j++) {          /*matrix.size()*/             for (int x = i; x < i + n; x++) {//i,i+n                 real_sum += matrix[x][j + m-1] - matrix[x][j - 1];       /*  -1  */             }             if (real_sum > result) {                 result = real_sum;             }         }     }     return result;
}

发表于 2019-04-12 09:33:11 回复(0)

HENG19

123123123123123

发表于 2019-04-10 17:21:28 回复(0)

Initialrole

 1 int maxSubmatrixSum(std::vector<std::vector<int>> matrix,  2                     int n, int m) {  3   int base_sum;  4   for (int i = 0; i < n; i++){  5     for (int j = 0; j < m; j++){  6       base_sum += matrix[i][j];  7     }  8   }  9   int result = 0; 10   for (int i = 0; i + n < matrix.size(); i++) { 11     if(i  > 0){ 12       for (int y = 0; y < m; y++){ 13         base_sum += matrix[i + n - 1][y] - matrix[i - 1][y]; 14       } 15     } 16     int real_sum = base_sum; 17     if (real_sum  > result) { 18       result = real_sum; 19     } 20     for (int j = 0; j + m < matrix.size(); j++) { 21       for (int x = 0; x < n; x++) { 22         real_sum += matrix[x][j + m] - matrix[x][j]; 23       } 24       if (real_sum > result) { 25         result = real_sum; 26       } 27     } 28   } 29   return result; 30 }

发表于 2019-03-15 15:11:01 回复(0)

n_m!!

  4   for(inti = 0; i < n; i++){ // 这里有错！改为 i < matrix.size() && i < n  
	
		5     for (int j = 0; j < m; j++){ // 这里也错！改为 j < matrix[0].size() && j < m  
	

	
		6       base_sum += matrix[i][j];  
	

	
		7     }  
	

	
		8   }
	

	
		11     if(i  > 0){
	

	
		12       for (int y = 0; y < m; y++){ // 这里有错！改为 y < matrix[0].size() && y < m
	

	
		13         base_sum += matrix[i + n][y] - matrix[i - 1][y];
	

	
		14       }
	

	
		15     } 
	

	
		// ...
	

	
		20     for (int j = 0; j + m < matrix.size(); j++) {
	

	
		         if(j > 0) { // 添加比较，避免越界
	

	
		21           for (int x = i; x < i+n; x++) { // 每次从i开始！！
	

	
		22             real_sum += matrix[x][j + m] - matrix[x][j - 1];
	

	
		23           }
	

	
		         }
	

	
		24       if(real_sum > result) {
	

	
		25         result = real_sum;
	

	
		26       }
	

	
		27     }

发表于 2018-08-22 22:34:05 回复(0)

杜比007

//采用累积和的思路即可

发表于 2018-05-10 14:43:58 回复(0)

cjaymj

发表于 2018-05-05 20:00:37 回复(0)

lukejr

1 int maxSubmatrixSum(std::vector<std::vector<int>> matrix,
2                     int n, int m) {
3   int base_sum;
4   for (int i = 0; i < n; i++){
5     for (int j = 0; j < m; j++){
6       base_sum += matrix[i][j];
7     }
8   }
9   int result = base_sum ;
10   for (int i = 0; i + n < matrix.size(); i++) {
11     if(i > 0){
12       for (int y = 0; y < m; y++){
13         base_sum += matrix[i + n][y] - matrix[i - 1][y];
14       }
15     }
16     int real_sum = base_sum;
17     if (real_sum > result) {
18       result = real_sum;
19     }
20     for (int j = 1; j + m < matrix.size(); j++) {
21       for (int x = 0; x < n; x++) {
22         real_sum += matrix[x][j + m] - matrix[x][j - 1];
23       }
24       if (real_sum > result) {
25         result = real_sum;
26       }
27     }
28   }
29   return result;
30 }

发表于 2018-03-28 22:53:05 回复(0)

提交观点

问题信息

上传者：小小

难度：

13条回答 60收藏 3564浏览

以下函数用于找到整数矩阵matrix中，元素之和最大的n行m

问题信息

热门推荐

相关试题