给定一个NxN矩阵mat和矩阵的阶数n，已知矩阵由正整数和负整数组成，请返回元素总和最大的子矩阵的元素之和。要求元素绝对值小于等于100000，尽量高效且矩阵阶数小于等于200。
测试样例：
[[1,2,-3],[3,4,-5],[-5,-6,-7]],3
返回：10
[编程题]最大和子矩阵
转换为单行求最大连续和问题。
class SubMatrix {
private:
int maxPartSum(vector<int>& nums)
{
int maxVal = nums[0],curVal = nums[0];
for (int i = 1; i < nums.size(); ++i)
{
if (curVal < 0) curVal = nums[i];
else curVal += nums[i];
maxVal = max({ maxVal, nums[i], curVal });
}
return maxVal;
}
public:
int sumOfSubMatrix(vector<vector<int>> mat, int n)
{
int maxSum = INT_MIN;
for (int i = 0; i < n; ++i)
{
vector<int> dp(mat[i]);
maxSum = max(maxSum, maxPartSum(dp));
for (int j = i + 1; j < n; ++j)
{
for (int k = 0; k < n; ++k) dp[k] += mat[j][k];
maxSum = max(maxSum, maxPartSum(dp));
}
}
return maxSum;
}
};
发表于 2017-07-05 10:41:11
回复(0)
class SubMatrix:
def sumOfSubMatrix(self, mat, n):
sMax = mat[0][0]
for i in xrange(n): # 上边界
A = [0] * n
for j in xrange(i, n): # 下边界
for c in xrange(n):
A[c] += mat[j][c]
sMax = max(sMax, subMax(A, n)) # 最大连续子数组，降为O(N^3)
return sMax
def subMax(A, n):
sMax, s = A[0], 0
for i in xrange(n):
s += A[i]
if s > sMax:
sMax = s
if s < 0:
s = 0
return sMax
发表于 2017-03-22 22:22:07
回复(0)
比较难想到的就是行累加后能够转变为一维数组求最大连续子数组和的问题。之后就是遍历所有行的组合就行了。
# -*- coding:utf-8 -*-
def find_max(arr):
if arr is None or len(arr) == 0:
return 0
max_sum = cur_sum = float('-inf')
for num in arr:
if cur_sum <= 0:
cur_sum = num
else:
cur_sum += num
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
"""
对每一行，与下面行累加，得到一个一维数组，用一维数组求连续子数组的最大和的方式求出最大和。O(N^2)
"""
def find_max_matrix(matrix, n):
if n <= 0:
return 0
max_sum = float('-inf')
row = len(matrix) # 行数
for i in range(row):
sum_arr = matrix[i]
cur_sum = find_max(sum_arr)
if cur_sum > max_sum:
max_sum = cur_sum
for j in range(i+1, row):
sum_arr = [sum_arr[x]+matrix[j][x] for x in range(len(sum_arr))]
cur_sum = find_max(sum_arr)
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
class SubMatrix:
def sumOfSubMatrix(self, mat, n):
return find_max_matrix(mat, n)
发表于 2019-03-20 11:47:10
回复(0)
本题根本上考查的 ----》求解数组中子序列的最大累加和。
如何将本题进行化简变为求最大累加和的问题呢？
将连续的两行的对应元素累加，求得到的累加和数组的最大累加和。依次遍历每种组合的可能，求总的最大累加和。
class SubMatrix {
public:
int max(int a,int b)
{
return a>b?a:b;
}
//求数组mat的最大累加和
int maxNumOfVector(vector<int> &mat,int n)
{
int res=numeric_limits<unsigned char>::min();
int curSum=0;
for(int i=0;i<n;i++)
{
curSum+=mat[i];
res=max(res,curSum);
if(curSum<0)
curSum=0;
}
return res;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int res=numeric_limits<unsigned char>::min();
for(int i=0;i<n;i++)
{
vector<int> sum(n);
for(int j=i;j<n;j++)
{
for(int k=0;k<n;k++)
{
sum[k]+=mat[j][k];
}
res=max(res,maxNumOfVector(sum,n));
}
}
return res;
}
};
发表于 2017-05-23 13:19:33
回复(0)
class SubMatrix {
public:
int check(vector<int> map, int max, int n){
vector<int> flag = map;
for(int j = 1; j < n; j++)
if(flag[j - 1] + map[j] > map[j])
flag[j] = flag[j - 1] + map[j];
for(int mm = 0; mm < n; mm++)
if(max < flag[mm])
max = flag[mm];
return max;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
long max = 0;
for(int k = 0; k < n; k++){
vector<int> map(n, 0);
map = mat[k];
max = check(map, max, n);
for(int i = k + 1; i < n; i++){
for(int j = 0; j < n; j++)
map[j] += mat[i][j];
max = check(map, max, n);
}
}
return max;
}
};
编辑于 2017-04-08 12:58:21
回复(0)
/*思路：
1.求子矩阵的最大和，首先得判定所有可能的子矩阵（纵向选定）
2.纵向选定后，将这块子矩阵按行累加压缩成一维，然后处理简单的一维（横向选定）
3.过程中有最大值出现即时更新即可
*/
public class SubMatrix {
public int sumOfSubMatrix(int[][] mat, int n) {
int maxSum = Integer.MIN_VALUE;
int sum[] = new int[mat[0].length];
for(int i=0; i<mat.length; i++){//压缩的起点
for(int j=0; j<sum.length; j++) sum[j]=0;//每次更换起点sum就重置，感觉还可改进
for(int t=0; t<mat.length-i; t++){//步长，矩阵=起点+步长
for(int j=0; j<sum.length; j++) sum[j]+=mat[i+t][j];//求上述矩阵的压缩和
maxSum = Math.max(maxSum, getMaxSum(sum)); //压缩为一维求和，取最大值
}
}
return maxSum;
}
public int getMaxSum(int a[]){//常用，一维数组中连续子数组的最大和int maxSum = Integer.MIN_VALUE;
int curSum = 0;
for(int i=0; i<a.length; i++){
curSum += a[i];
maxSum = Math.max(maxSum, curSum);
if(curSum<0) curSum=0;
}
return maxSum;
}
}
发表于 2016-08-20 18:02:23
回复(0)
利用动态规划，转成求一维数组最大连续子和的问题
减小规模： 枚举 从第i行到j行，找i-j行间的最大和子矩阵
问题转换：i-j行压缩成1行，每个数据是每列的累加和，然后就变成求这个一维数组的最大连续子和问题了
可以画下图，转换就很清楚了，代码如下：
减小规模： 枚举 从第i行到j行，找i-j行间的最大和子矩阵
问题转换：i-j行压缩成1行，每个数据是每列的累加和，然后就变成求这个一维数组的最大连续子和问题了
可以画下图，转换就很清楚了，代码如下：
#include<iostream>
#include<vector>
using namespace std;
class SubMatrix {
public:
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
// write code here
//cout << maxSumMat(mat) << endl;
return maxSumMat(mat);
}
int maxSumMat(vector<vector<int>> mat){
int n = mat.size();
int m = mat[0].size();
int res = 0;
vector<int> b = mat[0];
for (int i = 0; i < mat.size(); ++i)
{
for (int k = 0; k < mat[0].size(); ++k)
b[k] = 0;
for (int j = i; j < mat.size(); j++) //枚举i - j行
{
for (int k = 0; k < mat[0].size(); ++k){
b[k] += mat[j][k];
}
int maxSubMat = maxSumArray(b);
if (maxSubMat>res)
res = maxSubMat;
}
}
return res;
}
int maxSumArray( vector<int> data){
int cur= 0;
int max = cur;
int length = data.size();
for (int i = 0; i < length; i++){
if (cur>0){
cur+= data[i];
}
else{
cur= data[i];
}
if (cur > max)
max = cur;
}
return max;
}
};
发表于 2016-08-12 10:47:27
回复(2)
/*思路就是，（以第一行最为开始）先求第一行的最大和，然后将第二行数据加到第一行，
再求此时的最大值，然后再将下一行加上去，求最大值......最终得到第一列到最后一列的最大值；
还要计算第二行到最后一行的最大和，第三行到最后一行的最大和；
*/
class SubMatrix {
public:
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
// write code here
if(n<=0) return 0;
int maxVal = 0xffffffff;
for(int i=0;i<n;i++)
{
vector<int> temp(mat[i]);
maxVal=max(maxVal,helper(temp));//得到第一行的最大和
for(int j=i+1;j<n;j++)//循环下面的n-1行
{
for(int k=0;k<n;k++)//将行的n个元素加到上一行，然后计算最大和
{
temp[k]+=mat[j][k];
}
maxVal=max(maxVal,helper(temp));//依次0~k行的最大和
}
}
return maxVal;
}
//求连续数组最大和，动态规划思想
int helper(vector<int>& vec)//求一维数组最大和
{
int f=vec[0];
int result=f;
for(int i=1;i<vec.size();i++)
{
f=max(f+vec[i],vec[i]);
result=max(result,f);
}
return result;
}
};
发表于 2016-08-20 17:58:06
回复(7)
//时间复杂度为O(n^3),空间复杂度为O(n)
//把二维数组最大子矩阵和 转换成 一维数组的最大子数组：
/*把二维数组M x N 每一行分别相加，就可以得出一个一维数组(长度为N），
这个一维数组的最大子数组和就是原矩阵中包含M行X列的一个最大子矩阵和，
这样只用枚举出原N x N 矩阵的所有 M x N的子矩阵的最大子矩阵和，
就可以得出最后结果*/
class SubMatrix {
public:
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
int maxVal = -(1<<31);
for(int i = 0; i < n; i++){
vector<int> temp = mat[i];
maxVal = max(maxVal,helper(temp));
for(int j = i + 1; j < n; j++){
for(int k = 0; k < n; k++){
temp[k] += mat[j][k];
}
maxVal = max(maxVal,helper(temp));
}
}
return maxVal;
}
//找出该数组的最大子数组和
int helper(vector<int> &a){
int temp = a[0];
int maxVal = temp;
for(int i = 1; i < a.size(); i++){
if(temp < 0){
temp = a[i];
}else{
temp +=a[i];
}
if(temp > maxVal){
maxVal = temp;
}
}
return maxVal;
}
};
编辑于 2015-09-10 14:01:18
回复(0)
参考了 “忆水寒”的思路
class SubMatrix {
public:
int fundp(vector<int> mat)
{
int m=mat[0];
int res=m;
for(int i=1;i<mat.size();i++)//动态规划求出每一行的最大和
{
m=max(m+mat[i],mat[i]);
res=max(res,m);
}
return res;
}
//思路就是从第一行开始，依次求出前1行最大和，前2行最大和。。。前n行最大和
//然后从第二行开始，依次求出第2行最大和，2-3行最大和，2-4行最大和。。。，2-n行最大和
//从第三行开始，3，3-4，3-5。。。3-n行最大和
//。。。
//n行
//比较求出最大和
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
int maxv=0;
if(n<=0)
return -1;
for(int i=0;i<n;i++)
{
vector<int> temp(mat[i]);
maxv=max(maxv,fundp(temp));
for(int j=i+1;j<n;j++)
{
for(int k=0;k<n;k++)
{
temp[k]+=mat[j][k];
}
maxv=max(maxv,fundp(temp));
}
}
return maxv;
}
};
发表于 2017-10-06 10:31:46
回复(0)
import java.util.*;
public class SubMatrix {
public int sumOfSubMatrix(int[][] mat, int n) {
int max = Integer.MIN_VALUE;
for(int i = 0; i < n; i++) {
int[] temp = mat[i];
max = Math.max(max, helper(temp));
for(int j = i+1; j < n; j++) {
for(int k = 0; k < n; k++) {
temp[k] += mat[j][k];
}
max = Math.max(max, helper(temp));
}
}
return max;
}
int helper(int[] a) {
int temp = a[0];
int maxVal =temp;
for(int i = 1; i < a.length; i++) {
if(temp < 0) {
temp = a[i];
}else {
temp += a[i];
}
maxVal = temp > maxVal? temp : maxVal;
}
return maxVal;
}
}
发表于 2017-06-11 16:59:12
回复(0)
int sumOfSubMatrix(vector > mat, int n)
{
int max_sum=0;
for(int i=0;i<n;i++)
{
vectorsum(n);//从第j=i行开始，每一列的数进行累加得到的和
for(int j=i;j<n;j++)
{
for(int k=0;k<n;k++)
{
sum[k]+=mat[j][k];//累计和
}//for
max_sum=max(max_sum, helper(sum));
}//for
}//for
return max_sum;
}
int helper(vector nums)//一维数组最大值
{
if(nums.size()==0) return 0;
vectordp(nums.size());//动态规划标准解法
dp[0]=nums[0];
int max_val=nums[0];
for(int i=1;i<nums.size();i++)
{
dp[i]=max(nums[i], dp[i-1]+nums[i]);
max_val=max(dp[i], max_val);
}
return max_val;
}};
发表于 2022-03-26 22:28:47
回复(0)
class SubMatrix {
public:
int get(vector<vector<int>> &mat, vector<vector<int>> &sum, int x1, int y1, int x2, int y2) {
return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
int row = mat.size(), col = mat[0].size();
vector<vector<int>> sum(row + 10, vector<int>(col + 10, 0));
for (int i = 1; i <= row; ++ i) {
for (int j = 1; j <= col; ++ j) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int res = -0x3f3f3f3f;
for (int x1 = 1; x1 <= row; ++ x1) {
for (int y1 = 1; y1 <= col; ++ y1) {
for (int x2 = x1; x2 <= row; ++ x2) {
for (int y2 = y1; y2 <= col; ++ y2) {
//cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << get(mat, sum, x1, y1, x2, y2) << endl;
res = max(res, get(mat, sum, x1, y1, x2, y2));
}
}
}
}
return res;
}
};
发表于 2020-08-15 16:00:04
回复(0)
public class SubMatrix {
public int sumOfSubMatrix(int[][] mat, int n) {
// write code here
int rowCount = mat.length;
int columnCount = mat[0].length;
int[] partialSum = new int[columnCount];
int maxSum = Integer.MIN_VALUE;
for (int rowStart = 0; rowStart < rowCount; rowStart++) {
clearArray(partialSum);
for (int rowEnd = rowStart; rowEnd < rowCount; rowEnd++) {
for (int i = 0; i < columnCount; i++) {
partialSum[i] = partialSum[i] + mat[rowEnd][i];
}
int tempMaxSum = maxSubArray(partialSum);
maxSum = Math.max(maxSum,tempMaxSum);
}
}
return maxSum;
}
public int maxSubArray(int[] array) {
int maxSum = Integer.MIN_VALUE;
int runningSum = 0;
for (int i = 0; i < array.length; i++) {
runningSum = runningSum + array[i];
maxSum = Math.max(maxSum,runningSum);
if (runningSum < 0) {
runningSum = 0;
}
}
return maxSum;
}
public void clearArray(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = 0;
}
}
}
发表于 2019-02-17 23:41:56
回复(0)
//学高分大佬
class SubMatrix {
public:
int sumit(vector<int>& v, int n)
{
int tp=v[0];
int out=tp;
for(int i=1;i<n;i++)
{
tp=max(v[i],tp+v[i]);
out=max(out,tp);
}
return out;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int maxi=INT_MIN;
for(int i=0;i<n;i++)
{
vector<int> tp(mat[i]);
maxi=max(sumit(tp,n),maxi);
for(int j=i+1;j<n;j++)
{
for(int p=0;p<n;p++)
tp[p]+=mat[j][p];
maxi=max(sumit(tp,n),maxi);
}
}
return maxi;
}
};
发表于 2018-07-05 08:42:04
回复(0)
//按行压缩成数组，转化成求子数组最大累加和的问题
import java.util.*;
public class SubMatrix {
public int sumOfSubMatrix(int[][] mat, int n) {
// write code here
if(mat == null || n == 0) return 0;
int max = Integer.MIN_VALUE;
int cur = 0;
int[] s = null;
for (int i = 0; i < n; i++){
s = new int[n];
for (int j = i; j < n; j++){
cur = 0;
for (int k = 0; k < n; k++){
s[k] += mat[j][k];
cur += s[k];
if(cur > max) max = cur;
if(cur < 0) cur = 0;
}
}
}
return max;
}
}
发表于 2018-02-12 14:13:04
回复(0)
//时间复杂度为O(n^3) //详细原理参见：https://www.cnblogs.com/xiaoxi666/p/7341098.html class SubMatrix { public: int sumOfSubMatrix(vector<vector<int> > matrix, int n) { // write code here int max_sum=0; for(size_t i=0;i<matrix.size();++i) { vector<int> s(matrix[0].size()); for(size_t j=i;j<matrix[0].size();++j) { int sum_cur=0; for(size_t k=0;k<matrix[0].size();++k) { s[k]+=matrix[j][k]; sum_cur+=s[k]; sum_cur=sum_cur<0 ? 0 : sum_cur; max_sum=max(max_sum,sum_cur); } } } return max_sum; } };
编辑于 2017-08-10 20:12:52
回复(0)
class SubMatrix {
public:
int sumOfSubMatrix(vector<vector<int> > mat, int n) {
// write code here
int max = INT_MIN;
for(int i=0; i<n; ++i){
vector<int> tmp(n, 0);
for(int j=i; j<n; ++j){
for(int k=0; k<n; ++k) tmp[k]+=mat[j][k];
int temp = helper(tmp, n);
if(temp>max) max=temp;
}
}
return max;
}
private:
int helper(vector<int>& vec, int n){
vector<int> dp;
int max = INT_MIN;
for(int i=0; i<n; ++i){
int tmp;
if(i==0||dp[i-1]+vec[i]<vec[i]) tmp = vec[i];
else tmp = dp[i-1]+vec[i];
if(tmp>max) max=tmp;
dp.push_back(tmp);
}
return max;
}
};
发表于 2017-05-30 22:45:40
回复(0)
// vector中的最大值
int MaxOfVec(vector<int> v, int n)
{
int max = 0;
int cur = 0;
for (int i = 0; i < n; i++)
{
if (cur > 0)
cur += v[i];
else
cur = v[i];
max = max > cur ? max : cur;
}
return max;
}
int sumOfSubMatrix(vector<vector<int> > mat, int n)
{
// 遍历i-j行最大值
int res = 0;
vector<int> cij = mat[0];
for (int i = 0; i < n; i++)
{
for (int a = 0; a < n; a++)
cij[a] = 0;
for (int j = i; j < n; j++) // i->j最大值
{
for (int a = 0; a < n; a++)
cij[a] += mat[j][a];
int m = MaxOfVec(cij, n);
res = res > m ? res : m;
}
}
// 防止全为负整数
if (res == 0)
{
res = mat[0][0];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
res = res > mat[i][j] ? res : mat[i][j];
}
return res;
}
发表于 2017-04-26 13:59:28
回复(0)
class SubMatrix {
public:
int sumOfSubMatrix(vector<vector<int> > mat, int
n) {
// write code here
int min=-100000;
vector<vector<int> >
res(n,vector<int>(n,min));
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
res[i][j]=mat[i][j];
}
}
for (int i=0;i<n;i++){
vector<int> r(n,0);
vector<int> a(n);
for (int j=i;j<n;j++){
for (int k=0;k<n;k++){
r[k]=r[k]+res[j][k];
}
a=r;
for (int k=1;k<n;k++){
if (a[k]+a[k-1]>a[k])
a[k]=a[k]+a[k-1];
}
for (int e=0;e<n;e++){
if (a[e]>min)
min=a[e];
}
}
}
return min;
}
};
发表于 2017-03-29 09:41:40
回复(0)
问题信息
难度：
30条回答
97收藏
23961浏览
通过挑战的用户
查看代码-
2022-12-03 19:49:02 -
2022-11-02 10:27:44
-
2022-10-09 10:17:42 -
2022-09-14 10:12:35
-
2022-08-27 08:01:23
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
