算法：以最少的删除元素数按升序过滤出数字序列

Question

实际的问题上下文非常不同，但一般化的问题是试图找出一种算法，该算法按升序过滤需要最少数量的删除元素的数字序列。

应用该算法将如下所示。

wrong_sequence = [1,2,8,88,99,1,18,77,78,100,103]. # need to remove 88,99,1
correct_sequence = [1,2,8,18,77,78,100,103] # should NOT be [1,2,8,88,99]
enter code here

这不像循环遍历列表并检查列表的当前编号是否大于前一个编号那么简单，因为可能存在当前编号递增但应过滤掉的情况。

例如，虽然 88,99 是升序数字，但应将其从列表中删除。换句话说，[1,2,8,88,99] 不应该是答案，因为删除 1, 18, 77, 78, 100, 103 数字需要删除比删除 88,99,1[=11 更多的元素=]

如有指导，将不胜感激！

Answer 1

我认为您正在寻找的是经典的 LIS 问题 - 最长递增子序列。通过找到最长递增子序列，您还将得到问题的答案，即 n - l 其中 n 是数组的长度，而 l 是最长递增子序列的长度.
Here 是关于这个问题的更详细的 post。
这也是我对这个问题的看法：

#include <iostream>
#define NMAX int(1e5) //maximum size of array
#define INF int(1e9) // some large number
using namespace std;
int dp[NMAX],i,n,a[NMAX],max1,ans;
//max1 is the maximum length of the longest increasing subsequence
//dp[i] is the minimum value such that an increasing subsequence of length i ends in it
//because the values of dp[1],dp[2],dp[3],... are non-decreasing we can do a binary search
//to find our answer, thus getting a good time complexity -> O(nlog2n)
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>a[i];
    dp[0]=0;
    for(i=1;i<=n;i++)
    {
        dp[i]=INF;
        int st=0,dr=i-1,poz=0;
        while(st<=dr)
        {
            int m=(st+dr)/2;
            if(dp[m]<=a[i])
            {
                poz=m;
                st=m+1;
            }
            else dr=m-1;
        }
        dp[poz+1]=min(dp[poz+1],a[i]);
        max1=max(max1,poz+1);
    }
    ans=n-max1;
    cout<<ans<<" elements removed."<<endl;
    cout<<"The resulting array is: "<<endl;
    for(i=1;i<=max1;i++)
        cout<<dp[i]<<' ';
    return 0;
}

算法：以最少的删除元素数按升序过滤出数字序列

Algorithm: Filtering out a sequence of numbers in ascending order with least number of removed elements

algorithm

data-structures