最大子矩阵

提示：这里可以添加系列文章的所有文章的目录，目录需要自己手动添加
例如：第一章 Python 机器学习入门之pandas的使用

提示：写完文章后，目录可以自动生成，如何生成可参考右边的帮助文档

• 最大子矩阵
• • @[TOC](文章目录)
• 一、题目描述
• 二、分析

已知矩阵的大小定义为矩阵中所有元素的和。给定一个N*M矩阵，你的任务是找到最大的非空(大小至少是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行m列的矩阵，
[x00,x01,x01,x0m-1,…xn-1]假设最大的子列和是从i行到j行，从k列到l列(0<=i<=j<=n;0<=k<=l<=m)。我们可以先把i行都j行的元素按列加和，则问题就变成求解最大子列和问题

转化成

这样就变成求最大子列和的问题，最大子列和用动态规划即可解决。
比如数组a0,a1,…an-1。 dp[i]为a0到ai的最大子列和，
dp[i] = max(a[i],dp[i-1]+a[i]);

#include 
#include 
#include 
#include 
#include 

using namespace std;



int main()
{
    int n,m;
    cin>>n>>m;
    
    int matrix[n][m],sum[m],dp[m],maxSum;
    for(int i=0;i>matrix[i][j];
    maxSum=matrix[0][0];
    for(int i=0;i
        memset(sum,0,sizeof(sum));
        for(int j=i;j
            for(int k=0;k
                sum[k]+=matrix[j][k];
                dp[0]=sum[0];
                maxSum=max(dp[0],maxSum);
                for(int k=1;k
                    dp[k]=max(sum[k],dp[k-1]+sum[k]);
                    maxSum=max(dp[k],maxSum);
                }
            } 
        }
    }
    
    cout< 

---

# 总结
主要是能将二维数组转为一维数组，然后用动态规划求最大子列和