题目描述：

　　从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。

分析：

　　这可以用双端LIS方法来解决，先求一遍从左到右的，再求一遍从右到左的。最后从里面选出和最大的即可。

 

代码实现：

#include 
     
      using namespace std;int DoubleEndLIS(int *arr, int len){    int *LIS = new int[len];    int *lefToRight = new int[len];        //leftToRight[i]表示0~i最长子序列长度-1    int *rightToLeft = new int[len];    int maxLen = 0;        //记录总共的(上升+下降)最长子序列长度    int low, high, mid;    for (int i = 0; i < len; ++i)    {        lefToRight[i]  = 0;        LIS[i] = 0;    }    LIS[0] = arr[0];    for (int i = 1; i < len; i++)    {        low = 0; high = lefToRight[i-1];        while (low <= high)        {            mid = (low + high)/2;            if (LIS[mid] < arr[i])            {                low = mid + 1;            }             else            {                high = mid -1;            }        }        LIS[low] = arr[i];        if (low > lefToRight[i-1])        {            lefToRight[i] = lefToRight[i-1] + 1;    //最长子序列长度加1        }        else        {            lefToRight[i] = lefToRight[i-1];        }    }    //leftToRight的每个值增加1，因为他们是最长子序列值-1    //此时leftToRight表示的是最长子序列的真正值。    for (int i = 0; i < len; i++)    {        lefToRight[i]++;    }    //从右到左    for (int i = 0; i < len; i++)    {        rightToLeft[i] = 0;        LIS[i] = 0;    }    int k = 0;    LIS[0] = arr[len-1];    for (int i = len -2; i >= 0; --i)    {        low = 0; high = rightToLeft[k];        while (low <= high)        {            mid = (low + high)/2;            if (LIS[mid] < arr[i])            {                low = mid + 1;            }             else            {                high = mid - 1;            }        }        LIS[low] = arr[i];        if (low > rightToLeft[k])        {            rightToLeft[k+1] = rightToLeft[k] + 1;        }        else        {            rightToLeft[k+1] = rightToLeft[k];        }        ++k;    }    for (int i = 0; i < k; ++i)    {        rightToLeft[i]++;    }    //求最大值即为要求的    for (int i = 0; i < len; ++i)    {        cout<<"i: "<
      <<" "<
       
        <<"  "<
        
         <
         
           maxLen)            maxLen = lefToRight[i] + rightToLeft[len-i-1];    }    cout<<"maxLen:"<
          
           <
          
         
        
       
     

 

参考：

但是，他的程序有问题，我做了修改。