2021-10-03

求最大子矩阵（和最大的矩阵）
输入样例

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2

输出样例

15

思路

对于一维数组，用dp求最长公共子序列，dp[k]=max(dp[k-1]+a[k],a[k])
二维则是对行数遍历，对于第i行到第j行，求每一列的和，然后得到一个一维数组，求其最长公共子序列，所得最大值即为第i行到第j行中的最大子矩阵

代码

#include
#include
#include
#include
using namespace std;
typedef long long ll;
int a[105][105],summ[105][105],b[105],dp[105],anss,anss2;
int main(){
    int n;
    cin>>n;
    for(int i=0;i>a[i][j];
        }
    }
    memset(summ,0,sizeof(summ));
    for(int j=0;janss2){
                    anss2=dp[k];
                }
            }
            if(i==0&&j==0){
                anss=anss2;
            }
            else{
                anss=max(anss,anss2);
            }
        }
    }
    cout<