[编程题]最大子矩阵
- 热度指数：19036 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。
输入描述:
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。
输出描述:
输出最大子矩阵的大小。
示例1
输入
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
输出
15
思路
先写两重循环枚举起点行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)
将二维转化为一维做最大子数组和，代码时间复杂度为 。有 paper 研究可达到
，具体可以见 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)
https://blog.csdn.net/beiyeqingteng/article/details/7056687
这篇教程的思路很清晰
发表于 2020-06-06 12:13:03
回复(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)
#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)
使用动态规划，引入辅助矩阵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)
#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)
我的算法复杂度是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)
#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)
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)
/*
动态规划：最大子矩阵
求连续数组的最大和
思路：将二维的问题转换成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)
//动态规划,时间复杂度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)
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)
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)
#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)
二维版本的连续子数组最大和，使用动态规划求解
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));
int n = Integer.parseInt(br.readLine());
int[][] matrix = new int[n][n];
for(int i = 0; i < n; i++){
String[] row = br.readLine().split(" ");
for(int j = 0; j < n; j++)
matrix[i][j] = Integer.parseInt(row[j]);
}
int[][] calSum = new int[n][n]; // calSum[i][j]表示前i行第j列的元素之和
for(int i = 0; i < n; i++)
calSum[0][i] = matrix[0][i];
for(int i = 1; i < n; i++){
for(int j = 0; j < n; j++)
calSum[i][j] = calSum[i - 1][j] + matrix[i][j];
}
int maxSize = Integer.MIN_VALUE;
int[] colSum = new int[n];
for(int startRow = -1; startRow < n; startRow ++){
for(int endRow = startRow + 1; endRow < n; endRow ++){
// 接下来与求数组的连续子数组最大和相同
int tempSum = 0;
for(int col = 0; col < n; col ++){
// startRow=-1需要求取第一行在第col列的和，由于第一行没有前缀和做差，所以需要特殊处理
colSum[col] = startRow == -1? calSum[endRow][col]: calSum[endRow][col] - calSum[startRow][col];
tempSum = Math.max(colSum[col], colSum[col] + tempSum);
maxSize = Math.max(maxSize, tempSum);
}
}
}
System.out.println(maxSize);
}
}
发表于 2021-08-17 17:37:12
回复(0)
#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 <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin>>n;
vector<vector<int>> arr(n,vector<int>(n));
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
cin>>arr[i][j];
}
}
int res = arr[0][0];
for(int i=0; i<n; i++){ //从第i行开始
vector<int> temp(n,0);
for(int j=i; j<n; j++){ //第j行结束
int temp_max = -128, sum = temp_max; //记录 i~j行构成的子矩阵的最大值
for(int k=0; k<n; k++){
temp[k] += arr[j][k];
sum = max(sum+temp[k], temp[k]);
temp_max = max(temp_max, sum);
}
res = max(res, temp_max);
}
}
cout<<res;
return 0;
}
编辑于 2023-12-29 14:54:50
回复(0)
问题信息
难度：
83条回答
417收藏
26079浏览
通过挑战的用户
查看代码-
2023-03-06 16:32:23 -
2023-03-05 16:03:27 -
2023-02-10 16:33:35
-
2023-01-28 14:07:07 -
2022-12-27 15:16:11
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
