Native C++ solution, accepted!


  • 1
    W

    This solution is base on the artful array operation. This is the accepted code. I' will give you some details after the source code of the solution:

    class Solution {
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
            int ret = INT_MIN;
    
        	int col = matrix.size();
        	int row = matrix[0].size();
        
        	vector<vector<int>> sum_col(col+1, vector<int>(row+1, 0));
        
        	for (register int i = 0, ii = 1; i < col; i++, ii++){
        		for (register int j = 0, jj = 1; j < row; j++, jj++){
        				sum_col[ii][jj] = sum_col[i][jj] + matrix[i][j];
        		}
        	}
        
        	vector<int> col_sums(row + 1, 0);
        	for (register int i = 1; i <= col; i++){
        		for (register int j = 0; j < i; j++){
        			for (register int r = 1; r <= row; r++){
        				col_sums[r] = sum_col[i][r] - sum_col[j][r];
        			}
        			for (register int ii = 1; ii <= row; ii++){
        				int sum = col_sums[ii]; 
        				if (sum == k){
        					return k;
        				}
        				else if (sum < k && ret < sum){
        					ret = sum;
        				}
        				for (register int jj = ii - 1; jj > 0; jj--){
        					sum += col_sums[jj]; 
        					if (sum == k){
        						return k;
        					}
        					else if (sum < k && ret < sum){
        						ret = sum;
        					}
        				}
        			}
        		}
        	}
        	return ret;
        }
    };
    

    Details:
    Code 1, iterate all the rows. In every iteration marks the index as current row, and than sums all the rows which index are no bigger than the current row and restore the result in sum_col[current_index][row];

    code 1:
    
    vector<vector<int>> sum_col(col+1, vector<int>(row+1, 0));
    for (register int i = 0, ii = 1; i < col; i++, ii++){
        	for (register int j = 0, jj = 1; j < row; j++, jj++){
        		sum_col[ii][jj] = sum_col[i][jj] + matrix[i][j];
        	}
    }
    

    Code 2, iterate all the sum_col, try to choose 0 ~ current_index neighbors to have col neighbor sum.

    code 2:
    
    for (register int r = 1; r <= row; r++){
        	col_sums[r] = sum_col[i][r] - sum_col[j][r];
    }
    

    Code 3, try to choose 0~current_index col neighbors to get close to k.

    code 3:
    
    for (register int jj = ii - 1; jj > 0; jj--){
        	sum += col_sums[jj]; 
        	if (sum == k){
        		return k;
        	}
        	else if (sum < k && ret < sum){
        		ret = sum;
        	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.