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

逃离我推掉我的手 2022-08-07 14:42 10阅读 0赞

原文地址[http://blog.chinaunix.net/uid-26548237-id-3757779.html][http_blog.chinaunix.net_uid-26548237-id-3757779.html]

分析这个问题，首先要分析的问题是：寻找最长增长字串

1、寻找最长增长字串

分析这个问题，就要用动态规划。

进一步分析，动态规划过程，又会用到二分查找。

原文已经解释很清楚，在此不再赘述。只是自己在运行原文代码时，发现有问题。所以改正了一下，新代码如下。

#include<iostream>
    using namespace std;
    
    int MAX(int *LIS,int len)
    {
        int max = 0;
        for(int i = 0;i < len;++i)
        {
            cout<<i<<" "<<LIS[i]<<endl;
            if(LIS[i] > max)
                max = LIS[i];
        }
        return max;
    }
    
    int LIS0(int *array,int len)
    {
        int *LIS = new int[len];//用于记录当前各元素作为最大元素的最长递增序列长度
        for(int i = 0;i < len;++i)
        {
            LIS[i] = 1;//设置当前元素array[i]作为最大元素的最长递增序列长度为1
            for(int j = 0; j < i;++j)
            {
                if(array[i] > array[j] && LIS[j] + 1 > LIS[i])
                {
                    LIS[i] = LIS[j] + 1;
                }
            }
        }
        int res = MAX(LIS,len);
        delete LIS;
        return res;//获得LIS中的最大值并返回；
    }
    
    int LIS(int *array,int len)
    {
    	//LIS数组存储的是对应长度为i+1的最长子串的最小值，如LIS[3]=7,就是说当最长子串为4时，可以选数组里7这个数字
        int *LIS = new int[len];
        int left,mid,right;
        int max=1;
        LIS[0]=array[0];
        for(int i = 1;i < len;++i)
        {
            left = 0;
            right = max-1;
            while(left <=right)
            {
                mid = (left+right)/2;
                if(LIS[mid] < array[i])
                    left = mid +1;
                else
                    right = mid -1;
            }
            LIS[left] = array[i];//插入
            if(left >= max)
            {
                max++;
            }
        }
        delete LIS;
        return max;
    }
    //int main(int args,char ** argv)
    //{
    //	//int array[] = {1,2,3,4,5};
    //    //int array[] = {2, 1, 5 ,3 ,6 ,4 ,8 ,9, 7,8,9};
    //	int array[] = {1,4,3,5,6,7,2,0};
    //    int len = sizeof(array)/sizeof(int);
    //    int res = LIS(array,len);
    //    cout<<res<<endl;
    //    return 0;
    //}

2、回到原始问题  
分析原来的问题，只是在两个方向找最长递增子序列，然后找到一个最大值。代码如下

/* 
    *copyright@nciaebupt 转载请注明出处 
    *问题：从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。 
    *比如数列1,4,3,5,6,7,2,0 删除的最少的数的个数为1 
    *求解思路：双端LIS问题，使用动态规划的思路求解，时间复杂度O(nlog(n)) 
    */  
    #include <cstdio>  
    #include <iostream>  
      
    using namespace std;  
      
    int DoubleEndLIS(int *array,int len)  
    {  
        int left,mid,right;  
        int max=0;  
        int k =0;  
      
        //LIS数组中存储的是 递增子序列中最大值最小的子序列的最后一个元素（最大元素）对应array中的值  
        int *LIS = new int[len];  
        //从左到右LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是0~i的数字序列中最长递增子序列的长度-1  
        int *B = new int[len];  
        //从右到左LIS中最长子序列中最大值最小的子序列的最后一个元素所在的位置,也就是len-1~i的数字序列中最长递增子序列的长度-1  
        int *C = new int[len];  
        //从左到右  
        for(int i = 0;i < len;++i)//LIS数组清零  
        {  
            B[i] = 0;  
            LIS[i] = 0;  
        }  
        LIS[0] = array[0];  
        for(int i = 1;i < len;++i)  
        {  
            left = 0;  
            right = B[k];  
            while(left <= right)  
            {  
                mid = (left + right)/2;  
                if(array[i] < LIS[mid])  
                {  
                    right = mid - 1;  
                }  
                else  
                {  
                    left = mid + 1;  
                }  
            }  
      
            LIS[left] = array[i];//将array[i]插入到LIS中  
            if(left > B[k])  
            {  
                B[k+1] = B[k] + 1;  
                k++;  
            }else
    		{
    			B[k+1] = B[k];
    			k++;
    		}
        }  
        for(int i = 0;i <= k;++i)  
        {  
            B[i]++;  
        }  
        //从右到左  
        for(int i = 0;i < len;++i)//LIS数组清零  
        {  
            C[i] = 0;  
            LIS[i] = 0;  
        }  
        k = 0;  
        LIS[0] = array[len-1];  
        for(int i = len-2;i >= 0;--i)  
        {  
            left = 0;  
            right = C[k];  
            while(left <= right)  
            {  
                mid = (left + right)/2;  
                if(array[i] < LIS[mid])  
                {  
                    right = mid - 1;  
                }  
                else  
                {  
                    left = mid + 1;  
                }  
            }  
            LIS[left] = array[i];  
            if(left > C[k])  
            {  
                C[k+1] = C[k] + 1;  
                k++;  
    		}else{
    			C[k+1] = C[k];
    			k++;
    		}
        }  
        for(int i = 0;i <= k;++i)  
        {  
            C[i]++;  
        }  
      
        //求max  
        for(int i = 0;i < len;++i)  
        {    
            if(B[i]+C[len-1-i]>max)  
                max=B[i] + C[len-1-i]; 
    		cout<<B[i]<<"  "<<C[len-1-i]<<" "<<max<<endl;
        }  
      
        return len - max +1;  
    }  
      
    int main(int args,char ** argv)  
    {  
        int array[] = {1,2,8,9,4,3}; 
    	//int array[] = {1,2,4,3,5,6,7,2,0};
        int len = sizeof(array)/sizeof(int);  
        int res = DoubleEndLIS(array,len);  
        cout<<res<<endl;    
        return 0;  
    }

![Center][]  
![Image 1][]

通过看运行结果，可知，在某一点达到需要值，所以代码可行。

最后，感谢原文作者。

[http_blog.chinaunix.net_uid-26548237-id-3757779.html]: http://blog.chinaunix.net/uid-26548237-id-3757779.html
[Center]: /images/20220805/cbefb5faca8742e88b75d65f7d00204e.png
[Image 1]: