【题解】【最长上升子序列+树状数组】

【通过分析题目可以得知，最优情况应该是一段子序列或两段子序列。这样一来就比较好做了。正着做一遍最长上升子序列，再倒着做一遍。枚举点，判断是一段优还是两段优。】

【由于朴素的最长上升子序列是O(n^2)的，会T，所以用树状数组加速成O(nlogn)】

#include
    
     #include
     
      #include
      
       using namespace std;double tree[100010],f[100010],g[100010],ans;int a[100010],num[100010],n,m;inline int lowbit(int x){    return (x&(-x));}inline void add(int x,double val){    for(int i=x;i<=n;i+=lowbit(i))     if(tree[i]
       
        0;i-=lowbit(i))     if(tree[i]>sum) sum=tree[i];    return sum;}int main(){    int i,j;    scanf("%d",&n);    for(i=1;i<=n;++i)scanf("%d",&a[i]),num[i]=a[i];    sort(num+1,num+n+1);    m=unique(num+1,num+n+1)-num-1;    for(i=1;i<=n;++i)     {        int x=lower_bound(num+1,num+m+1,a[i])-num;        double tmp=ask(x);        f[i]=tmp+a[i];        add(x+1,f[i]);     }    memset(tree,0,sizeof(tree));    for(i=n;i>0;--i)     {        int x=lower_bound(num+1,num+m+1,a[i])-num;        double tmp=ask(x);        g[i]=tmp+a[i];        add(x+1,g[i]);     }    for(i=1;i<=n;++i)     {        ans=max(ans,f[i]*1.0);        ans=max(ans,(f[i]+g[i]-(double)a[i])/2.0);     }    printf("%.3lf\n",ans);    return 0;}