题解 | 隔板与水槽

枚举左右两侧最大容积，相加得最大容积

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<long long>l_max(n,0);
    vector<long long>r_max(n,0);
    for(int k=1;k<n;k++){
        long long max_v=0;
        for(int i=0;i<k;i++){
            long long v=min(a[i],a[k])*(k-i);
            max_v=max(max_v,v);
        }
        l_max[k]=max_v;
    }
    for(int k=0;k<n-1;k++){
        long long max_v=0;
        for(int i=k+1;i<n;i++){
            long long v=min(a[k],a[i])*(i-k);
            max_v=max(max_v,v);
        }
        r_max[k]=max_v;
    }
    long long ans=0;
    for(int k=1;k<n-1;k++){
        ans=max(ans,l_max[k]+r_max[k]);
    }
    cout<<ans<<endl;
}