给一个长度为n的序列，要求删除一个连续子序列，使剩下的序列有一个长度最大的连续递增子序列。

最简单的想法是枚举起点j和终点i，然后数一数，分别向前或向后能延伸的最长长度，记为g(i)和f(i)。可以先预处理出每一个点能往前和往后延伸的长度(g(i)和f(i))。然后枚举终点i，快速找一个g(j)最大的起点。如果有两个候选的起点，一个j，一个j‘，A[j']<=A[j]且g[j']>g[j]，那么j一定可以排除，g(j')更大，而且更容易拼接。

固定i的情况下，所有有价值的(A[j],g(j))按照A[j]排序（A[j]相同的值保留g(j)大的那个），将会形成一个有序表，根据之前的结论g(j)是递增的，有序，那么二分查找就派上用处了。

然后再考虑，变动i对之前的有序表的影响，i增加，把之前的A[i],g(i)加入到有序表中，如果满足A[i']比它A[i]小且g(i')最大的二元组，即它前面的一个元素，满足g(i')>=g(i)，那么这个元素不该保留。否则应该加入这个二元组，加入这个二元组之后，为了保持有序表的性质，还要往后检查删除一些g(i*)小的元素。

终于想得比较透彻了，实现方式是set，用pair来保证二元组，pair比较的时候是先比较第一维，相等时才比较第二维。至于第二种实现，用数组保存g(j)对应最小的A[j]值，复习LIS时再补上吧~

 

#include
     
      #define MP make_pair#define se second#define fi firstusing namespace std;const int maxn = 2e5+5;typedef pair
      
        pii;int A[maxn];int g[maxn];//<-int f[maxn];//->//set
       
         s;map
        
          s;int main(){    int T; scanf("%d",&T);    while(T--){        int n; scanf("%d",&n);        for(int i = 0; i < n; i++) scanf("%d",A+i);        if(n == 1) { printf("1\n"); continue; }        g[0] = 1;        for(int i = 1; i < n; i++) {            if(A[i]>A[i-1]) g[i] = g[i-1]+1;            else g[i] = 1;        }        f[n-1] = 1;        for(int i = n-2; i >= 0; i--) {            if(A[i]
         
          ::iterator it = s.lower_bound(A[i]);            bool keep = true;            if(it!=s.begin()){                it--;                ans = max(ans,it->se+f[i]);                keep = it->se < g[i];            }            if(keep){                //s.erase(cur);                it = s.insert({A[i],g[i]}).fi;                it++;                while(it != s.end() && it->se <= g[i] ) s.erase(it++);            }        }        printf("%d\n",ans);    }    return 0;}
         
        
       
      
     

set_插入前要erase，因为set里的元素是不支持修改的，insert的返回值是itertor,bool

#include
     
      #define MP make_pair#define se second#define fi firstusing namespace std;const int maxn = 2e5+5;typedef pair
      
        pii;int A[maxn];int g[maxn];//<-int f[maxn];//->set
       
         s;int main(){    int T; scanf("%d",&T);    while(T--){        int n; scanf("%d",&n);        for(int i = 0; i < n; i++) scanf("%d",A+i);        if(n == 1) { printf("1\n"); continue; }        g[0] = 1;        for(int i = 1; i < n; i++) {            if(A[i]>A[i-1]) g[i] = g[i-1]+1;            else g[i] = 1;        }        f[n-1] = 1;        for(int i = n-2; i >= 0; i--) {            if(A[i]
        
         ::iterator it = s.lower_bound(cur);            bool keep = true;            if(it!=s.begin()){                it--;                ans = max(ans,it->se+f[i]);                keep = it->se < cur.se;            }            if(keep){                s.erase(cur);                it = s.insert(cur).fi;                it++;                while(it != s.end() && it->se <= cur.se ) s.erase(it++);            }        }        printf("%d\n",ans);    }    return 0;}
        
       
      
     

 类似LIS的写法，非常简洁的感觉

#include
     
      using namespace std;const int maxn = 2e5+5;int f[maxn],g[maxn];//前，后int a[maxn];int v[maxn];const int INF = 0x3f3f3f3f;int main(){    int Z; cin>>Z;    while(Z--){        int n; scanf("%d",&n);        for(int i = 0; i < n; i++) scanf("%d",a+i);        f[0] = 1;        for(int i = 1; i < n; i++)            f[i] = 1 + (a[i] > a[i-1] ? f[i-1] : 0);        g[n-1] = 1;        for(int i = n-1; i--; )            g[i] = 1 + (a[i] < a[i+1] ? g[i+1] : 0);        int ans = 0;        for(int i = 0; i < n; i++){            v[1+i] = INF;            int k = lower_bound(v+1,v+1+i,a[i])-v-1;            ans = max(ans,k+g[i]);            v[f[i]] = min(v[f[i]],a[i]);        }        printf("%d\n",ans);    }    return 0;}