题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5696

解题思路

大致思路：
找到区间[l,r]的最小值的位置p，确定了区间[l,r]的最小值为a[p]，那么区间[l,r]内包含p点的任意子区间都要通过a[p]去乘以某个此子区间的最大值得到此子区间价值吧。
很显然，value[p,i]=max(value[p,j],a[p]*a[j+1])，
解释一下，假设p<j，那么由于所有区间的最小值都是a[p]，那么区间价值只取决于最大值的大小，而位于p同侧的大区间的价值比小区间的价值大，要么相等；（你想想是不是）
更新完以区间[l,r]中最小值为分界点的ans之后，分别对p的左、右半区间递归。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+100;
ll tmp[N],a[N],ans[N];
int n;
void dfs(int L,int R){
    if(L>R) return ;
    int pos=L;
    ll maxx=0;
    for(int i=1;i<=R-L+1;i++) tmp[i]=0; //初始化tmp数组为0
    for(int i=L;i<=R;i++) if(a[pos]>a[i]) pos=i;//找到区间[l,r]中最小值的位置
    for(int i=L;i<=pos;i++) tmp[pos-i+1]=max(tmp[pos-i+1],a[pos]*a[i]); //tmp的索引为区间长度，pos左半区间每个位置的值乘上区间[l,r]的最小值。此式中取最大值操作的意义与直接赋值含义相同。
    for(int i=pos;i<=R;i++) tmp[i-pos+1]=max(tmp[i-pos+1],a[pos]*a[i]);//pos的右半区间，每个位置的值乘上区间[l,r]的最小值，同时tmp取同区间长度下较大的乘积。
    for(int i=1;i<=R-L+1;i++){
        maxx=max(maxx,tmp[i]);//小区间的tmp最大值如果比大区间的tmp最大值还大，让大区间的最大值也等于小区间的最大值。//比较精髓的地方
        ans[i]=max(ans[i],maxx);//刷新最终的区间最大值
    }
    dfs(L,pos-1);//去掉pos点，找左半区间的最小值再进行上述操作。
    dfs(pos+1,R);//去掉pos点，找右半区间的最小值再进行上述操作。
    return ;
}
int main(){
    while(cin>>n){
        memset(ans,0,sizeof ans);
        memset(a,0,sizeof a);
        for(int i=1;i<=n;i++) cin>>a[i];
        dfs(1,n);
        for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    }
}