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

我不是女神ヾ 2021-11-29 18:00 149阅读 0赞

题目描述：

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

分析：

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

代码实现：

#include <iostream>
    
    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: "<<i<<" "<<lefToRight[i]<<"  "<<rightToLeft[len-i-1]<<endl;
            if (lefToRight[i] + rightToLeft[len-i-1] > maxLen)
                maxLen = lefToRight[i] + rightToLeft[len-i-1];
        }
        cout<<"maxLen:"<<maxLen<<endl;
    
        delete LIS;
        delete lefToRight;
        delete rightToLeft;
    
        return len - maxLen + 1;
    }
    
    int main()
    {
        int arr[] = {
        1,5,7,6,9,3,8,4,2};
        int ret;
        ret = DoubleEndLIS(arr, 9);
        cout<<ret<<endl;
    
        return 0;
    }

参考：[http://blog.csdn.net/nciaebupt/article/details/8466049][http_blog.csdn.net_nciaebupt_article_details_8466049]

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

转载于:https://www.cnblogs.com/Jason-Damon/p/4012021.html

[http_blog.csdn.net_nciaebupt_article_details_8466049]: http://blog.csdn.net/nciaebupt/article/details/8466049