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

lis2.md

##LIS变种

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

###思路

• 双 LIS 问题，用DP可解，目标规划函数 max{ l[i] + r[i]}, 其中

   l[i] 为从左到右， 0 ~ i 个数之间满足递增的数字个数
   r[i] 为从右到左， n-1 ~ i 个数之间满足递增的数字个数
  

• 最后结果为 n + 1 - max

###复杂度

• 使用二分搜索可以优化至O(logn)
• 使用STL的lower_bound缩减代码

###Code

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    int DLIS2(vector<int>& a)
    {
    	int n = a.size();
    	vector<int> dp(n,INT_MAX);
    	vector<int> l(n,INT_MIN);
    	vector<int> r(n,INT_MIN);
    	//Left to right
    	for(auto i = 0; i < n; ++i)
    	{
    		auto it = lower_bound(dp.begin(),dp.begin()+n,a[i]);
    		*it = a[i];
    		l[i] = it - dp.begin() + 1;
    	}
    	//Right to left
    	fill(dp.begin(),dp.end(),INT_MAX);
    	for(auto i = n-1; i >= 0; --i)
    	{
    		auto it = lower_bound(dp.begin(),dp.begin()+n,a[i]);
    		*it = a[i];
    		r[i] = it - dp.begin() + 1;
    	}
    	int max = 0;  
        for (auto i = 0; i < n; ++i )  
    	{
            if (l[i]+r[i] > max) max = l[i] + r[i];  
    	}
    	return n+1-max;
    }
    int DLIS1(vector<int>& a)
    {
    	int i,low, high, mid, max;  
    	int n = a.size();
        vector<int>		b(n,-1);
    	vector<int>		c(n,-1);
    	vector<int>		inc(n,INT_MAX);  
          
          
        for (i = 0; i < n; ++i) 
    	{  
            low = 0; high = i;  
            while (low < high) 
    		{  
                mid = low + (high-low)*0.5;  
                if (inc[mid] < a[i])
    			{
    				low = mid + 1;  
    			}
                else 
    			{
    				high = mid;  
    			}
            }  
            b[i] = low + 1;  
            inc[low] = a[i];  
        }  
          
    	for (i = 0; i < n; ++i) 
    	{
    		inc[i] = INT_MAX;
    	}
        for (i = n-1; i >= 0; --i) 
    	{  
            low = 0; high = i;  
            while (low < high) 
    		{  
                mid = low + (high-low)*0.5;  
                if (inc[mid] < a[i])
    			{
    				low = mid + 1;  
    			}
                else 
    			{
    				high = mid; 
    			}
            }  
            c[i] = low + 1;  
            inc[low] = a[i];  
        }  
        max = 0;  
        for (i = 0; i < n; ++i )
    	{
            if (b[i]+c[i] > max) max = b[i] + c[i];  
    	}
        return n+1-max; 
    }
    int main()
    {
    	int a[20] = {1,10,2,9,3,8,4,7,5,6,6,5,7,4,8,3,9,2,10,1};
    	vector<int> test(a,a+20);
    	cout<<"(Naive DLIS)Remove "<<DLIS1(test)<<"  elements\n";
    	cout<<"(Using  STL)Remove "<<DLIS2(test)<<"  elements\n";
    	system("pause");
    	return 0;
    }