发表于 2019-04-24 代码:1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn = 500000+10;const LL inf = 1e17;int n;int i,j;LL sum[maxn],stmx[maxn][23],stmn[maxn][23];int a[maxn],l[maxn],r[maxn];stack<int> sta;LL askmx(int l,int r){ int k=log2(r-l+1); return max(stmx[l][k],stmx[r-(1<<k)+1][k]);}LL askmn(int l,int r){ int k=log2(r-l+1); return min(stmn[l][k],stmn[r-(1<<k)+1][k]);}int main(){ scanf("%d",&n); for (i=1;i<=n;i++) scanf("%d",&a[i]); for (i=1;i<=n;i++) sum[i]=sum[i-1]+(LL)a[i]; for (i=0;i<=n;i++) stmx[i][0]=stmn[i][0]=sum[i]; for (j=1;(1<<j)<=n+1;j++){ for (i=0;i+(1<<j)-1<=n;i++){ stmx[i][j]=max(stmx[i][j-1],stmx[i+(1<<(j-1))][j-1]); stmn[i][j]=min(stmn[i][j-1],stmn[i+(1<<(j-1))][j-1]); } } for (i=1;i<=n;i++){ while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop(); if (sta.empty()) l[i]=1; else l[i]=sta.top()+1; sta.push(i); } while (!sta.empty()) sta.pop(); for (i=n;i>=1;i--){ while (!sta.empty()&&a[i]<=a[sta.top()]) sta.pop(); if (sta.empty()) r[i]=n; else r[i]=sta.top()-1; sta.push(i); } LL ans=-inf; for (i=1;i<=n;i++){ if (a[i]<0){ LL R=askmn(i,r[i]); LL L=askmx(l[i]-1,i-1); ans=max(ans,(R-L)*(LL)a[i]); } else if (a[i]>0){ LL R=askmx(i,r[i]); LL L=askmn(l[i]-1,i-1); ans=max(ans,(R-L)*(LL)a[i]); } else{ ans=max(ans,0ll); } } printf("%lld\n",ans); system("pause"); return 0;} 打赏 微信支付 支付宝