记录一下今天做的相关题目（思路均参考相关题目的题解）

$acwing$矩形牛棚

直方图中最大的矩形模型
用dp处理出高度，单调栈维护区间长度

类似题目： 直方图中最大的矩形 玉蟾宫

最大正方形类

[最大正方形](https://www.luogu.com.cn/problem/P1387)

这类题：    
【法一】可以用二维前缀和 枚举边长
【法二】用 dp 状态表示为正方形右下角[i,j]的最大正方形边长，
注意转移过程中取min,否则会遇到“障碍”,可以想想因为正方形
的缘故，木桶的“短板效应”。
【法三】搜索

【法一】前缀和

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,a[N][N],s[N][N],ans=-1;
bool check(int x,int y)
{
    return x<=n&&y<=m;
}
int main()
{
    cin>>n>>m;
    int len=min(n,m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
    cin>>a[i][j];
    s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];    
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            for(int l=1;l<=len;l++)//枚举边长
            {
                int x=i+l-1,y=j+l-1;
                if(!check(x,y)||(s[x][y]-s[x][j-1]-s[i-1][y]+s[i-1][j-1])!=(l*l))break;//剪枝
                ans=max(ans,l);
            }
        }
    }
    cout<<ans;

    return 0;
}

【法二】dp

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,g[N][N],dp[N][N],ans=-1;
int f(int a,int b,int c)
{
if(a>b)swap(a,b);
if(a>c)swap(a,c);
return a;
}
//种树那道，是从下边界去向上找最大直方矩形，这类题正方形从右下角来找
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>g[i][j];

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(g[i][j])dp[i][j]=f(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1;
            ans=max(dp[i][j],ans);
        }
    }
    cout<<ans;
    return 0;
}

【法三】搜索

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,a[N][N];
int x_1,y_1,ans,res=-1;
int dfs(int x,int y)
{
    for(int i=x_1;i<=x;i++)
    if(!a[i][y])return 0;//向右边搜，遇到障碍（0）终止
    for(int i=y_1;i<=y;i++)
    if(!a[x][i])return 0;
    ans=dfs(x+1,y+1)+1;//成功了边长+1
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j])//值为1作为左上角开始右和下搜
            {
                x_1=i,y_1=j;//左上角
                ans=0;//每次搜索重置
                res=max(res,dfs(i,j));
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

类似题目： 巨大的牛棚 奶牛浴场
求最大字段和

//双段的，无非就是从前和从后去维护最多前后缀
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e7+10;
int n,x[N],a[N],b[N];//注意起点
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>x[i];
    a[1]=x[1];
    for(int i=2;i<=n;i++)a[i]=max(a[i-1]+x[i],x[i]);
    for(int i=2;i<=n;i++)a[i]=max(a[i-1],a[i]);//最大前缀
    b[n]=x[n];
    for(int i=n-1;i>0;i--)b[i]=max(b[i+1]+x[i],x[i]);
    for(int i=n-1;i>0;i--)b[i]=max(b[i+1],b[i]);
    int ans=a[1]+b[2];//从最后一个数开始
    for(int i=2;i<n;i++)//因为去转移的时候，[i-1,i+1]所以[2,n-1]   
    ans=max(ans,a[i-1]+b[i+1]);
    cout<<ans;
    return 0;
}