楼上大佬单调栈解法太强了 能不能帮忙看看我的代码是否可行，应该是O(nlogn)的复杂度。 dp[i]表示 以i为结尾的子序列的最大值的和 const int maxn = 1e5+7; typedef long long ll; int pos[maxn]; int val[maxn*10]; ll dp[maxn*10]; int max_pos(int s, int e) { if(s > e) return -1; if(s == e) return pos[s]; int mid = s + (e-s)/2; int l = max_pos(s,mid); int r = max_pos(mid+1,e); return l > r ? l : r; } int main() { int n; while(~scanf("%d",&n)) { int mx = -1; for(int i = 0;i < n;i ++) { scanf("%d",val+i); mx = max(mx,val[i]); } double sum = 0; memset(pos,-1,sizeof(pos)); for(int i = 0;i < n;i ++) { int p = max_pos(val[i]+1,mx); pos[val[i]] = i; if(p == -1) dp[i] = val[i] * 1LL * (i-p); else dp[i] = dp[p] + val[i] * 1LL * (i-p); sum += dp[i]; } sum = 2*sum / ((n+1) * n); printf("%.6lf\n",sum); } return 0; }