最大子矩阵_

Python

TimeMac

try:
    while True:
        num = int(input())
        matrix = []
        for i in range(num):
            matrix.append(list(map(int,input().split())))
        maxSubMatrix = 0
        for i in range(num):
            array = [0] * num           #i行到j行之间同列的相加
            for j in range(i,num):
                for q in range(num):    #j每次加一array都会继承前面的，只有i变化时才重置array
                    array[q] += matrix[j][q]
                temp = array[0]
                ans = array[0]
                for k in range(1,num):  #对之前得到的i行到j行同列中找最大连续和
                    temp= max(temp+array[k],array[k])
                    ans = max(temp,ans)
                if maxSubMatrix < ans:
                    maxSubMatrix = ans
        print(maxSubMatrix)
except Exception:
    pass

编辑于 2018-10-03 18:02:06 回复(1)

C/C++

牛客448905766号

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
int yiwei(vector<int> w)//一维最大连续和函数；
{
int n = w.size(); vector<int> y(n); y[0] = w[0]; int ma=w[0];
for(int x=1;x<n;++x)
{
y[x] = max(w[x], y[x - 1] + w[x]);
}
for(int x=1;x<n;++x)
ma = max(ma, y[x]);
return ma;
}
vector<int> merge(int i,int j, vector<vector<int>> juz)//从i行合并到j行；
{
if (i == j)return juz[i];
int len = juz[0].size();
vector<int> a(len);
for(int m=i;m<=j;++m)
{
for(int n=0;n<len;++n)
{
a[n] += juz[m][n];
}
}
return a;
}
int math(vector<vector<int>> juz)//求最大子矩阵
{
int ma = -50000,l;
int len = juz.size();
for(int i=0;i<len;++i)
{
for(int j=i;j<len;++j)
{
l = yiwei(merge(i, j, juz));
ma = max(ma, l);
}
}
return ma;
}
int main() {//子矩阵的最大和
int n, k; scanf("%d", &n); vector<vector<int>> juz(n,vector<int>(n));
for(int i=0;i<n*n;++i)
{
scanf("%d", &k); juz[i / n][i % n] = k;
}
cout << math(juz)<< endl;
return 0;
}

编辑于 2022-03-23 13:02:28 回复(0)

C++

之一不之

#include<bits/stdc++.h>
using namespace std;
const int maxn=130;
int maxtia[maxn][maxn];
int total[maxn][maxn];
int dp[maxn];
int a[maxn];

int MaxSub(int n){
    int maximum;
    for(int i=0;i<n;i++){
        if(i==0){
            dp[i]=a[i];
            maximum=a[i];
        }else{
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}

int MaxMaxitra(int n){
    int maxx=0;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            for(int k=0;k<n;k++){
                if(i==0){
                    a[k]=total[j][k];
                }else{
                    a[k]=total[j][k]-total[i-1][k];
                }
            }
            int current=MaxSub(n);
            maxx=max(current,maxx);
        }
    }
    return maxx;
}

int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>maxtia[i][j];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==0){
                    total[i][j]=maxtia[i][j];
                }else{
                    total[i][j]=total[i-1][j]+maxtia[i][j];
                }
                
            }
        }
        int ans=MaxMaxitra(n);
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2021-08-30 23:10:49 回复(0)

domeya

思路

先写两重循环枚举起点行k1到终点行k2，再写一个循环遍历每列i，将列i压缩成一个数字，它表示第i列k1~k2行的前缀和（用二维前缀和预处理），那么就变成了一个1*n的矩阵，即一个一维数组，然后求其最大子段和，同时取max即可。

时间复杂度O(n^3)。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=510,inf=1e18;
typedef long long ll;
ll a[N][N],sum[N][N],dp[N];
int main()
{
    ios::sync_with_stdio(false);
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+a[i][j]; // 第j列前i行的前缀和
        }
    }
    ll mx=-inf;
    for(int k1=1;k1<=n;k1++) // 行 上端点
    {
        for(int k2=k1;k2<=n;k2++) // 行 下端点
        {
            //dp[0]=0;
            for(int i=1;i<=n;i++) // 列
            {
                ll tmp=sum[k2][i]-sum[k1-1][i]; // 第i列 [k1,k2]行之和
                dp[i]=max(dp[i-1]+tmp,tmp); // 最大子段和求法
                mx=max(mx,dp[i]);
            }
        }
    }
    printf("%lld\n",mx);
    return 0;
}
/*
3
-1 -4 3
3 4 -1
-5 -2 8
ans:10

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2
ans:15
*/

编辑于 2021-07-13 21:55:28 回复(0)

牛客404270893号

将二维转化为一维做最大子数组和，代码时间复杂度为 $O(n^3)$ 。有 paper 研究可达到 $O(n^{2.82..})$ ，具体可以见 Wiki。

#include 
#include 
#include 
#include 
using namespace std;
class Solution {
public:
    int maxSubMatrix(vector>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        // 1. 处理列前缀和
        vector> colPrefix(n, vector (m + 1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                colPrefix[j][i+1] = colPrefix[j][i] + matrix[i][j];
            }
        }
        // 2. 枚举行子矩阵
        int maxSum = 0;
        for (int row1 = 0; row1 < m; ++row1) {
            for (int row2 = row1; row2 < m; ++row2) {
                // 做一位 maxSubArray
                int maxSoFar = colPrefix[0][row2+1] - colPrefix[0][row1], maxEndHere = maxSoFar;
                for (int j = 1; j < n; ++j) {
                    maxEndHere = max(maxEndHere, 0) + colPrefix[j][row2+1] - colPrefix[j][row1];
                    maxSoFar = max(maxSoFar, maxEndHere);
                }
                maxSum = max(maxSum, maxSoFar);  // 更新该子矩阵最大区域和
            }
        }
        return maxSum;
    }
};
int main() {
    int n;
    cin >> n;
    vector> nums(n, vector (n, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> nums[i][j];
        }
    }
    cout << Solution().maxSubMatrix(nums) << endl;
    return 0;
}

编辑于 2021-02-23 20:24:26 回复(0)

MEMESOREREMEREDODOLA

https://blog.csdn.net/beiyeqingteng/article/details/7056687

这篇教程的思路很清晰

发表于 2020-06-06 12:13:03 回复(0)

C/C++

YX不会coding

#include<iostream>
(720)#include<algorithm>
using namespace std;
const int maxn=105;
int matrix[maxn][maxn];
int total[maxn][maxn];//辅助数组，记录原始矩阵从上到下加起来的累加矩阵
int a[maxn];//一维数组
int dp[maxn];//设dp[i]表示以a[i]作为末尾的连续序列的最大和
int MaxSubSequence(int n)
{
    int maximum=-0xffff;
    for(int i=0;i<n;i++)
    {
        if(i==0)//最大和的连续子序列只有一个即a[i]本身
            dp[i]=a[i];
        else{//最大和的连续序列有多个元素，即dp[i]=a[j]+...+a[i-1]+a[i];
            //而dp[i-1]=a[j]+...+a[i-1];
            //所以可以得到下面的状态转移方程
            dp[i]=max(dp[i-1]+a[i],a[i]);//状态转移方程
        }
        maximum=max(maximum,dp[i]);
    }
    return maximum;
}
int MaxSubMatrix(int n)
{
    int maxx=-0xffff;
    //假设最大子矩阵所在的行是从i到j
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)//从小到大枚举并遍历i和j行
        {
            for(int k=0;k<n;k++)//获得一维数组a[k];
            {
                if(i==0){
                    a[k]=total[j][k];
                }else{
                    a[k]=total[j][k]-total[i-1][k];//获得从第i行到j行的各个元素累加和
                }
            }
            int current=MaxSubSequence(n);//对从i行到j行的元素依次累加起来得到的一维数组求最大子序列和
            maxx=max(maxx,current);//求遍历完所有i,j行中的最大值
        }
    }
    return maxx;
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>matrix[i][j];
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)//初始化辅助数组
            {
                if(i==0)
                    total[i][j]=matrix[i][j];
                else{
                    total[i][j]=total[i-1][j]+matrix[i][j];
                }
            }
        int ans=MaxSubMatrix(n);
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2020-04-07 17:29:59 回复(0)

楚梦西

#include<cstdio>
(802)#include<iostream>
#include<algorithm>
(831)#include<cstring>
using namespace std;
int a[101][101];
int total[101][101];
int arr[101];
int dp[101];
int main(){
	int n;
    while(scanf("%d",&n)!=EOF){
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			scanf("%d",&a[i][j]);
			}
		}
		for(int i=0;i<n;i++){//第i行 
			for(int j=0;j<n;j++){//第j列 
				if(i==0) total[i][j]=a[i][j];//第0-i行第j列子矩阵和 
				else total[i][j]=a[i][j]+total[i-1][j];
			}
		}	
		int m1=-999;//某i-j行最大的子矩阵 
		int m=-999;//整个矩阵最大的子矩阵 
		for(int i=0;i<n;i++){//第i行 
			for(int j=i;j<n;j++){//第j行 
				for(int k=0;k<n;k++){//第k列 
					if(i==0) arr[k]=total[j][k];
					else arr[k]=total[j][k]-total[i-1][k];//第i-j行第k列子矩阵和 
				}
				for(int p=0;p<n;p++){//对某i-j行 0-k列比较 得到max 
					if(p==0) dp[p]=arr[p];
					else dp[p]=max(arr[p],dp[p-1]+arr[p]);
					m1=max(m1,dp[p]);
				}
				m=max(m,m1);
			}
		}
		printf("%d\n",m);	
		
	}
return 0;
}

发表于 2020-03-04 14:45:03 回复(0)

C/C++

牛客480180948号

#include <iostream>
#include <cmath>
#include <limits>
using namespace std;

const int max_size = 100;

int dp1[max_size];  //一维数组的最大连续子序列动态规划
int row[max_size];  
int find_max_sum_1(const int& n){  //求一维数组的和最大连续子序列
	dp1[0] =row[0];
	int max_sum =row[0];
	for(int i=1;i<n;i++){
		dp1[i]=max(dp1[i-1]+row[i],row[i]);
		max_sum = max(max_sum,dp1[i]);
	}
	return max_sum;
}

int matrix[max_size][max_size];//存储二维数组，已经求和过了的

int main(){ 
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				cin>>matrix[i][j];
				if(i!=0){
					matrix[i][j] += matrix[i-1][j];
				}
			}	
		}

		int ans =numeric_limits<int>::min();
		for(int i=0;i<n;i++){    //对第i行到第j行之间组成的子数组，转换为一维数组后求最大连续子序列和
			for(int j=i;j<n;j++){
				if(i==0)
					copy(matrix[j],matrix[j]+n,row);
				else
					for(int k=0;k<n;k++)
						row[k] = matrix[j][k]-matrix[i-1][k];

				ans = max(ans,find_max_sum_1(n));
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

动态规划二维转换为一维，时间复杂度N^3，空间复杂度N^2

编辑于 2020-02-28 11:48:40 回复(0)

C/C++

pumpkin_1024

使用动态规划，引入辅助矩阵total[ ][ ]，是由原始矩阵matrix[ ][ ]从上到下加下来的。

如果我们要求第 i 行到第 j 行之间上下值的和，我们可以通过total[j][k] - total[i-1][k] 得到, k 的范围从0 到n-1。

#include<iostream>
using namespace std;

const int MAXN = 101;

int matrix[MAXN][MAXN];	//原始矩阵 
int total[MAXN][MAXN];	//辅助矩阵 
int arr[MAXN];			//一位数组 
int dp[MAXN]; 			

int MaxSubsequence(int n)	//求最大子序列和 
{
	int maximum = 0;
	for(int i=0; i<n; i++)
	{
		if(i==0)
		{
			dp[i] == arr[i];
		}
		else
		{
			dp[i] = max(arr[i], dp[i-1] + arr[i]);
		}
		maximum = max(maximum, dp[i]);
	}
	return maximum;
 } 
 
int MaxSubmatrix(int n)
{
	int maximal = 0;
	for(int i=0; i<n; i++){
		for(int j=i; j<n; j++){
			for(int k=0; k<n; k++){	//获得一维数组
				if(i == 0)
				{
					arr[k] = total[j][k];
				 } else{
				 	arr[k] = total[j][k] - total[i-1][k];
				 }
			}
			int current = MaxSubsequence(n);
			maximal = max(maximal, current);
		}
	} 
	return maximal;
} 

int main()
{
	int n;
	while(cin>>n)
	{
		for(int i=0; i<n; i++)
		{
			for(int j=0; j<n; j++)
			{
				cin>>matrix[i][j];
			}
		}
		for(int i=0; i<n; i++)	//初始化辅助函数 
		{
			for(int j=0; j<n; j++)
			{
				if(i == 0)
				{
					total[i][j] = matrix[i][j];
				}
				else
				{
					total[i][j] = total[i-1][j] + matrix[i][j];
				}
			}		
		}
		int answer = MaxSubmatrix(n);
		cout<<answer<<endl;
	}
	return 0;
}

但只通过了80%的测试用例，求大佬看看为什么？

发表于 2020-02-28 11:28:32 回复(2)

可可希尔

#include<iostream>
using namespace std;

#define MAXN 100

int gs_ls(int *A, int lo, int hi) { //计算[lo, hi)的最大切片和
    int gs = A[lo], s = 0, i = hi;
    while (lo < i--) {
        s += A[i];
        if (gs < s) gs = s;
        if (s < 0) s = 0;
    }
    return gs;
}

int main() {
    int n;
    int matrix[MAXN + 1][MAXN + 1]; //第i行 = 输入矩阵前i行的和
    while (cin >> n) {
        //计算matrix
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n ; j++) {
                int e; cin >> e;
                matrix[i][j] = matrix[i-1][j] + e;
            }
        
        //int dp[MAXN][MAXN]; //dp[i][j] = 输入矩阵第i行~第j行的最大子矩阵的和
        int gsm = gs_ls(matrix[1], 1, n+1);
        int A[MAXN]; //遍历i,j，A[...]记录输入矩阵第i行~第j行的和 = matrix[j][...] - matrix[i-1][...]
        //计算dp[i][j]
        for (int i = 1; i <= n ;i++)
            for (int j = i; j <= n ;j++) {
                if (i == 1 && j == 1) continue; //gsm初始化时已经计算过第1行的最大切片和

                for (int t= 1; t <= n ;t++) A[t] = matrix[j][t] - matrix[i-1][t];
                gsm = max(gsm, gs_ls(A, 1, n+1));
            }
        cout << gsm << endl;
    }
    return 0;
}

O(n^3)

发表于 2020-01-30 11:43:29 回复(0)

相信梦想

参考了  牛友：serene_12的代码  #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//主要思想是将二维数组压缩到一维数组，然后采用动态规划来求一维数组连续子元素最大和
//一维数组最大连续子元素和：https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
int ConsequentMaxNum(vector<int> numbers)
{
    int length = numbers.size();
    int tempSum = numbers[0],maxSum = numbers[0];
    for(int i=1;i<length;i++)
    {
        tempSum = (tempSum>0)? tempSum + numbers[i]: numbers[i];
        maxSum = (maxSum>tempSum)? maxSum: tempSum;
    }
    return maxSum;
}
int MergeConsequentMaxNum(vector<vector<int>> vec,int i,int j,int cols)
{
    vector<int> array(cols);   //生成cols个int的vector且都初始化为0
    for(int p=i;p<=j;p++)
        for(int q=0;q<cols;q++)
            array[q] += vec[p][q];    //压缩行到一行，全部加到列上去
    int ans = ConsequentMaxNum(array);
    return ans;
}
int GetMaxSubMatrix(vector<vector<int>> vec,int cols)
{
    int Max = vec[0][0];
    int temp;   //临时储存压缩后一维数组的最大连续和
    for(int i=0;i<cols;i++)   //从0行到第N行，双重递归O(n^2)
        for(int j=i;j<cols;j++)
        {
            temp = MergeConsequentMaxNum(vec,i,j,cols);
            if(temp>Max)
                Max = temp;
        }
    return Max;
}
int main()
{
    int N;
    cin>>N;
    vector<vector<int>> vec(N,vector<int>(N));  //N个元素都是含N个元素的vector
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            cin>>vec[i][j];
        }
    int result = GetMaxSubMatrix(vec,N);
    cout<<result;
    return 0;
}

编辑于 2018-07-21 00:15:53 回复(0)

serene_12

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

//要求一个二维矩阵的最大子矩阵，首先要会求一维矩阵的最大子矩阵（即一维数组连续最大和）
//假设原二维矩阵的最大子矩阵所在的行为i到j
//  1 当i = j时，则最大子矩阵为第i行的连续最大和
//  2 当i != j时，现在我们已经直到最大子矩阵的行，要求的是其所在的列
//      我们把从第i行到第j行的所有行相加，得到一个只有一行的一维数组，则该一维数组
//      的连续最大和就是最大子矩阵。

//求一维数组的连续最大和
//动态规划问题，设DP[i]=以v[i]元素结尾的连续最大和
//则DP[i] = max(DP[i-1] + v[i], v[i])
//初始条件为DP[0] = v[0]
int ConsequentMaxNum(vector<int> v){
    int N = v.size();
    vector<int> DP(N);
    DP[0] = v[0];
    for(int i = 1; i < N; i++)
        DP[i] = max(DP[i-1] + v[i], v[i]);
    int ans = DP[0];
    for(int i = 1; i < N; i++)
        if(ans < DP[i])
            ans = DP[i];
    return ans;
}

//把矩阵v的第i行到第j行进行合并，并求出连续最大和，N为矩阵v的列数
int MergeConsequentMaxNum(vector<vector<int>> v, int i, int j, int N){
    vector<int> array(N);
    for(int p = i; p <= j; p++)
        for(int q = 0; q < N; q++)
            array[q] += v[p][q];
    int ans = ConsequentMaxNum(array);
    //return DP(array, N);
    return ans;
}

int GetMaxSubMatrix(vector<vector<int>> v, int N){
    int MAX = 0, temp;
    for(int i = 0; i < N; i++)
        for(int j = i; j < N; j++)
            if((temp = MergeConsequentMaxNum(v, i, j, N)) > MAX)
                MAX = temp;
    return MAX;
}

int main()
{
    //freopen("data.txt", "r", stdin);
    int N;
    while(scanf("%d", &N) != EOF){
        vector<vector<int>> v(N, vector<int>(N));
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                scanf("%d", &v[i][j]);
        printf("%d\n", GetMaxSubMatrix(v, N));
    }
    return 0;
}

发表于 2018-03-18 20:40:03 回复(4)

263保洁小妹

我的算法复杂度是O(n*n*n)，不知道有没有O(n*n)的方案。由于n很小（才100），所以问题不大。

我的思路就是把问题抽象成求一维数组的最大连续子序列和，先把矩阵看成一个个1行的序列，分别求最大和；再把每相邻的两行合并(相加)成一行，然后求最大和；然后把相邻的3行XXX……直到相邻n行

#include <stdio.h>
#define N 100
#define INF 1E9
int martix[N][N];//存储矩阵
int buf[N];//将相邻若干行合并成一行以后的结果
int n, max;//n是矩阵大小，max是最大矩阵和

void FindMax(int from, int m)
{//从from行开始的连续m行合并，得到其最大连续序列和
    for(int i=0; i<n; i++) buf[i]=0;
    for(int j=0; j<n; j++)
    {
        for(int i=0; i<m; i++)
        {
            buf[j]+=martix[from+i][j];
        }
    }
    int sum=0;
    int maxHere=buf[0];
    for(int i=0; i<n; i++)
    {
        sum+=buf[i];
        if(sum>maxHere) maxHere=sum;
        if(sum<0) sum=0;//和为负，则全部丢弃，从下一个开始新的序列
    }
    if(maxHere>max) max=maxHere;//有必要的话修改max值
    return;
}

int main()
{
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        max=-INF;
        for(int i=0; i<n; i++)
        {//读取矩阵
            for(int j=0; j<n; j++)
            {
                scanf("%d", &martix[i][j]);
            }
        }
        for(int m=1; m<=n; m++)
        {//m是要合并连续的几行
            for(int from=0; from+m-1<n; from++)
            {//从from行开始合并连续的m行，并修改最大值
                FindMax(from, m);
            }
        }
        printf("%d\n", max);//输出结果
    }
}

发表于 2018-03-05 22:38:15 回复(4)

Adherer要加油呀~

#include <stdio.h>
#include <string.h>
#define MAX(a, b) (a > b ? a : b)
#define N 105
#define INF 0x3f3f3f3f
int martix[N][N];           //存储矩阵
int buf[N];                 //将相邻若干行合并成一行以后的结果
int n, maxSum;              //n是矩阵大小，maxSum是最大矩阵和
 
// 这里就是求解最大连续子段和
int findMax() {
   int i;
   int result = buf[0], sum = buf[0];
   for (i = 1; i < n; i++) {
       if (sum <= 0) {
           sum = buf[i];            //如果前面位置最大连续子序列和小于等于0，则以当前位置i结尾的最大连续子序列和为buf[i]  
       } else {
           sum += buf[i];           //如果前面位置最大连续子序列和大于0，则以当前位置i结尾的最大连续子序列和为它们两者之和
       }    

       result = MAX(result, sum);   //更新最大连续子序列和  
   }
   return result;
}
 
int main() {
    int i, j, k;
    while(scanf("%d", &n) != EOF) {
        if(n <= 0) {
            break;
        }
        maxSum = -INF;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &martix[i][j]);
            }
        }
        for(i = 0; i < n; i++) {
            // 数组b表示j ~ n - 1行，对应列元素的和
            // 将二维动态规划问题转化为一维动态规划问题
            memset(buf, 0, sizeof(buf));
            for(j = i; j < n; j++) {
                for(k = 0; k < n; k++) {
                    buf[k] += martix[j][k];
                }
                maxSum = MAX(findMax(), maxSum);
            }
        }
        printf("%d\n", maxSum);
    }
}

时间复杂度O(

)

发表于 2019-02-20 18:09:12 回复(0)

Java

嘿，man

import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int [][] matrix = new int[N][N];
        for(int i = 0;i<N;i++){
            for(int j = 0;j<N;j++){
                matrix[i][j] = in.nextInt();
            }
        }
        System.out.println(getMaxNum(matrix));
    }
    private static int getMaxNum(int[][] a) {
        int res = 0;
        if (a == null || a.length == 0 || a[0].length == 0) {
            return res;
        }
        int[] temp = null;
        res = Integer.MIN_VALUE;
        int max = 0;
        for (int i = 0; i < a.length; i++) {
            temp = new int[a[0].length];
            for (int j = i; j < a.length; j++) {
                max = 0;
                for (int k = 0; k < a[0].length; k++) {
                    temp[k] += a[j][k];
                    max = Math.max(max + temp[k], temp[k]);
                    res = Math.max(res,max);
                }
            }
        }

        return res;
    }
}

发表于 2020-01-26 22:32:43 回复(0)

C/C++

idutura

/*
    动态规划：最大子矩阵
    求连续数组的最大和
    思路：将二维的问题转换成1维，首先要先学会求一维数组的
    最大连续子序列和
    如果题目变成二维，那么我们假设最大连续子序列和在
    第i行到第j行，那么最优子结构有两种情况
    1.如果i==j，那么不用多说，结果就是第i行的最大连续子序列和
    2.如果i！=j，那么就求从i行到第j行同一列所有元素加起来的和
    将问题变成一个一维数组，这样再继续求这个一维数组的最大连续子序列和即可
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 110;
int matrix[maxn][maxn]; // 保存数组
int temp[maxn][maxn]; // 辅助数组，temp[i][j]保存矩阵前i行j列所有元素的和
int dp[maxn]; // 用于记录最大连续子序列和
int arr[maxn]; // 用于记录那个我们将问题转换后的一维数组
int getMaxSubSequence(int n){ // 求一维数组最大连续子序列和
	int ans = INT_MIN;
	for(int i=0;i<n;i++){
		if(i==0) dp[i] = arr[i];
		else dp[i] = max(arr[i],dp[i-1]+arr[i]);
		ans = max(ans,dp[i]);
	}
	return ans;
}
int getMaxSubMatrix(int n){
	int ans = INT_MIN;
	for(int i=0;i<n;i++){ // 计算从第i行开始至末尾行的最大连续子序列和
		for(int j=i;j<n;j++){
			for(int k=0;k<n;k++){ // 初始化arr
				if(i==0) arr[k] = temp[j][k]; // 如果是第一行
				/*
                    因为temp记录的是从0行到末尾所有行同列元素之和
                    那么如果起始行不是0行，那么要减掉i行之前的元素和
				*/
				else arr[k] = temp[j][k] - temp[i-1][k]; 
			}
			ans = max(ans,getMaxSubSequence(n));
		}
	}
	return ans;
}
int main() {
	int n;
	while(~scanf("%d",&n)) {
		for(int i=0; i<n; i++) { // input
			for(int j=0; j<n; j++) {
				scanf("%d",&matrix[i][j]);
			}
		}
		for(int i=0; i<n; i++) { // 初始化辅助数组
			for(int j=0; j<n; j++) {
				if(i==0) temp[i][j] = matrix[i][j];
				else temp[i][j] = temp[i-1][j] + matrix[i][j];
			}
		}
		printf("%d\n",getMaxSubMatrix(n));
	}
}

发表于 2020-03-23 16:50:01 回复(0)

SaulZhang98

//动态规划,时间复杂度O(n^3)
#include <iostream>
#include <climits>
#define N 100
using namespace std;
int buf[N][N];
int tmp[N][N];//辅助矩阵，其中tmp[i][j]存储的是前i行的第j列的累加之和
int b[N];
int max(int a,int b){return a>b?a:b;}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>buf[i][j];
        }
    }
    for(int i=0;i<n;i++)//初始化第一行
        tmp[0][i]=buf[0][i];
    for(int i=1;i<n;i++){
        for(int k=0;k<n;k++){
            tmp[i][k]=tmp[i-1][k]+buf[i][k];//累加上一行的值求和
        }
    }
    int maxsum = INT_MIN;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            int cursum=0;
            for(int k=0;k<n;k++){
                if(i==0){
                    b[k]=tmp[j][k];
                }
                else{
                    b[k]=tmp[j][k]-tmp[i-1][k];//得到第i行到第j行的累加之和
                }
                cursum=max(b[k],b[k]+cursum);
                maxsum=max(maxsum,cursum);
            }
        }
    }
    cout<<maxsum<<endl;
    return 0;
}

编辑于 2019-04-02 20:26:11 回复(0)

fengzhk

import java.util.Scanner;
public class Main{
    public static int Sum(int[] arr){
        int res = Integer.MIN_VALUE;
        int cur = 0;
        for(int i = 0;i < arr.length;i++){
            cur += arr[i];
            res = Math.max(res,cur);
            if(cur < 0)
                cur = 0;
        }
        return res;
    }
    public static int MaxRect(int[][] arr){
        int max = Integer.MIN_VALUE;
        int m = arr.length;
        int n = arr[0].length;
        for(int i = 0 ;i < m ;i++){
            int[] temp = new int[n];
            for(int j = i;j < m;j++){
               for(int k = 0;k < n;k++){
                   temp[k] += arr[j][k];
               }
               max = Math.max(max,Sum(temp));
            }
        }
        return max;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] rec = new int[N][N];
        for(int i = 0 ;i < N;i++)
            for(int j = 0;j < N;j++)
                rec[i][j] = sc.nextInt();
                     System.out.println(MaxRect(rec));
    }
}

发表于 2018-02-27 00:22:23 回复(1)

kestars

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;


//求连续数组最大和，动态规划思想
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;
}


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 main(){
	int N;
	while(scanf("%d",&N)!=EOF){
		vector<vector<int>> mat(N,vector<int>(N));
		for(int i=0;i<N;i++)

			for(int j=0;j<N;j++)
				scanf("%d",&mat[i][j]);
		int result=sumOfSubMatrix(mat,N);
		printf("%d\n",result);
	}
	return 0;
}

发表于 2016-10-26 16:07:53 回复(0)

最大子矩阵

输入描述:

输出描述:

输入

输出

思路

AC代码

问题信息

热门推荐

通过挑战的用户

相关试题