这是LIS的变形，题意是求一个序列中去掉某个连续的序列后，能得到的最长连续递增序列的长度。

　　用DP的解法是：吧这个序列用数组a来记录，再分别用两个数组f记录以i结尾的最长连续递增序列的长度，g[i]记录以i开头的最长连续递增序列。

然后像求DP求LIS一样遍历整个序列求出i前面所有小于a[i]的元素中以该元素结尾的最长序列f[j], 那么 dp[i] = g[j] + f[i], 这样时间复杂度为O（n^2)。

　　因为和普通的LIS相似，所以能够利用LIS的优化方法把该题的时间复杂的优化到O(nlogn)。方法仍是利用一个数组d[i]记录长度为 i 的连续递增序列的最后一个元素的最小值，显然该序列是单调递增的。所以上面红色字体的操作能够通过二分查找直接得到f[j]的值，进而得到一个可行的长度ans, 然后更新数组d就可以,更新的方法是假设以a[i]小于数组d中记录的与a[i]长度同样的序列的最后一个元素的值。那么把这个值改为a[i], 即  d[f[i]] = min(a[i], d[f[i]]);  终于ans的最大值即为答案。

　　代码例如以下：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int MAXN = 200050;const int INF = 1 << 30;int a[MAXN], f[MAXN], g[MAXN], d[MAXN];int main(){    int t, n, i;    scanf("%d", &t);    while(t--)    {        scanf("%d", &n);        for(i = 1; i <= n; i++)            scanf("%d", &a[i]);        f[1] = 1;        for(i = 2; i <= n; i++)            if(a[i] > a[i - 1])                f[i] = f[i - 1] + 1;            else                f[i] = 1;        g[n] = 1;        for(i = n - 1; i > 0; i--)            if(a[i] < a[i + 1])                g[i] = g[i + 1] + 1;            else                g[i] = 1;        int ans = 0;        for(i = 0; i <= n; i++)            d[i] = INF;         //d[i]的值所有赋值为INF，方便二分查找和更新d[i]        for(i = 1; i <= n; i++)        {            int len = (lower_bound(d + 1, d + 1 + i, a[i]) - (d + 1)) + g[i];            ans = max(len, ans);            d[f[i]] = min(a[i], d[f[i]]);        }        printf("%d\n", ans);    }    return 0;}