楼上大佬单调栈解法太强了 能不能帮忙看看我的代码是否可行，应该是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; }