在O(nlgn)时间复杂度内求最长非降子序列。

Question

在O(nlgn)时间复杂度内求最长非降子序列。

7

我有一个算法，它运行良好。我尝试为自己解释它（http://nemo.la/?p=943），并且在这里（http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/）以及stackoverflow上也有解释。

我想修改它以生成最长的非单调递增子序列。

对于序列30 20 20 10 10 10 10，

答案应该是4：“10 10 10 10”。

但使用nlgn版本的算法无法工作。将s初始化为包含第一个元素“30”，从第二个元素=20开始。这是发生的情况：

1. 第一步：30不大于或等于20。我们找到大于20的最小元素。新的s变成“20”。 2. 第二步：20大于或等于20。我们扩展序列，现在s包含“20 20”。 3. 第三步：10不大于或等于20。我们找到大于10的最小元素，即“20”。新的s变成“10 20”。

之后s将永远不会增长，算法将返回2而不是4。

int height[100];
int s[100];

int binary_search(int first, int last, int x) {

    int mid;

    while (first < last) {

        mid = (first + last) / 2;

        if (height[s[mid]] == x)
            return mid;

        else if (height[s[mid]] >= x)
            last =  mid;

        else
            first = mid + 1;
    }
    return first; /* or last */
}

int longest_increasing_subsequence_nlgn(int n) {

    int i, k, index;

    memset(s, 0, sizeof(s));

    index = 1;
    s[1] = 0; /* s[i] = 0 is the index of the element that ends an increasing sequence of length  i = 1 */

    for (i = 1; i < n; i++) {

        if (height[i] >= height[s[index]]) { /* larger element, extend the sequence */

            index++; /* increase the length of my subsequence */
            s[index] = i; /* the current doll ends my subsequence */

        }
        /* else find the smallest element in s >= a[i], basically insert a[i] in s such that s stays sorted */
        else {
            k = binary_search(1, index, height[i]);

            if (height[s[k]] >= height[i]) { /* if truly >= greater */
                s[k] = i;
            }
        }
    }
    return index;
}

- user1781626

“非单调递增序列”是指非严格递增吗？也就是说，对于每个 i>j：x[i]>=x[j]？” - Anton

是的，抱歉我表达不清楚了：应该是“非递减”的意思。 - user1781626

7个回答

5

您的代码基本上可以工作，除了在您的binary_search()函数中存在一个问题，该函数应返回第一个大于目标元素(x)的元素的索引，因为您想要最长的非递减序列。将其修改为以下内容即可。

如果您使用c ++，std :: lower_bound()和std :: upper_bound()将帮助您摆脱这个令人困惑的问题。顺便说一句，“if（height[s [k]]> = height [i]）”语句是多余的。

int binary_search(int first, int last, int x) {

    while(last > first)
    {
        int mid = first + (last - first) / 2;
        if(height[s[mid]] > x)
            last = mid;
        else
            first = mid + 1;
    }

    return first; /* or last */
}

- jfly

4

只需将最长递增子序列算法应用于有序对(A[i], i)，使用字典比较即可。

- Ukkonen

2

我的Java版本：

  public static int longestNondecreasingSubsequenceLength(List<Integer> A) {
    int n = A.size();
    int dp[] = new int[n];
    int max = 0;
    for(int i = 0; i < n; i++) {
        int el = A.get(i);
        int idx = Arrays.binarySearch(dp, 0, max, el);
        if(idx < 0) {
            idx = -(idx + 1);
        }
        if(dp[idx] == el) { // duplicate found, let's find the last one 
            idx = Arrays.binarySearch(dp, 0, max, el + 1);
            if(idx < 0) {
                idx = -(idx + 1);
            }
        }
        dp[idx] = el;
        if(idx == max) {
            max++;
        }
    }
    return max;
}

- boneash

1

这个问题的完全不同解决方案如下。复制数组并排序。然后计算数组中任意两个元素之间的最小非零差异（这将是相邻数组元素之间的最小非零差异），称为δ。此步骤需要O(n log n)的时间。

关键观察是，如果您将0添加到原始数组的第0个元素，将δ/n添加到原始数组的第二个元素，将2δ/n添加到数组的第三个元素等，则原始数组中的任何非递减序列都变成新数组中的严格递增序列，反之亦然。因此，您可以以这种方式转换数组，然后运行标准的最长递增子序列求解器，其运行时间为O(n log n)。此过程的净结果是找到最长非递减子序列的O(n log n)算法。

例如，考虑30, 20, 20, 10, 10, 10, 10。在这种情况下，δ = 10，n = 7，因此 δ / n ≈ 1.42。新数组是：

40, 21.42, 22.84, 14.28, 15.71, 17.14, 18.57

这里，LIS 是 14.28、15.71、17.14、18.57，对应于原始数组中的 10、10、10、10。

希望这能有所帮助！

- templatetypedef

0

如果您知道LIS的算法，那么在代码中更改不等式就可以得到最长非递减子序列。

LIS的代码：

public int ceilIndex(int []a, int n, int t[], int ele){
    int l=-1, r=n+1;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(a[t[mid]]<ele) l=mid;
        else r=mid;
    }
    return r;
}

public int lengthOfLIS(int[] a) {
    int n=a.length;
    int index[]=new int[n];
    int len=0;
    index[len]=0;
    int reversePath[]=new int[n];
    for(int i=0;i<n;i++) reversePath[i]=-1;
    for(int i=1;i<n;i++){
        if(a[index[0]]>=a[i]){
            index[0]=i;
            reversePath[i]=-1;
        }else if(a[index[len]]<a[i]){
            reversePath[i]=index[len];
            len++;
            index[len]=i;
        }else{
            int idx=ceilIndex(a, len, index, a[i]);
            reversePath[i]=index[idx-1];
            index[idx]=i;
        }
    }
    for(int i=0;i<n;i++) System.out.print(reversePath[i]+" ");
    System.out.println();
    // printing the LIS in reverseFashion
    // we iterate the indexes in reverse
    int idx=index[len];
    while(idx!=-1){
        System.out.print(a[idx]+" ");
        idx=reversePath[idx];
    }
    return len+1;
}

最长非降子序列的代码：

public int ceilIndex(int []a, int n, int t[], int ele){
    int l=-1, r=n+1;
    while(r-l>1){
        int mid=l+(r-l)/2;
        if(a[t[mid]]<=ele) l=mid;
        else r=mid;
    }
    return r;
}

public int lengthOfLongestNonDecreasingSubsequence(int[] a) {
    int n=a.length;
    int index[]=new int[n];
    int len=0;
    index[len]=0;
    int reversePath[]=new int[n];
    for(int i=0;i<n;i++) reversePath[i]=-1;
    for(int i=1;i<n;i++){
        if(a[index[0]]>a[i]){
            index[0]=i;
            reversePath[i]=-1;
        }else if(a[index[len]]<=a[i]){
            reversePath[i]=index[len];
            len++;
            index[len]=i;
        }else{
            int idx=ceilIndex(a, len, index, a[i]);
            reversePath[i]=index[idx-1];
            index[idx]=i;
        }
    }
    for(int i=0;i<n;i++) System.out.print(reversePath[i]+" ");
    System.out.println();
    // printing the LIS in reverseFashion
    // we iterate the indexes in reverse
    int idx=index[len];
    while(idx!=-1){
        System.out.print(a[idx]+" ");
        idx=reversePath[idx];
    }
    return len+1;
}

- Ganesh Chowdhary Sadanala

0

我用C++中的上界函数提供了最长非降子序列的简单解决方案。时间复杂度为(nlogn)

int longest(vector<long long> a) {
    vector<long long> s;
    s.push_back(a[0]);
    int n = a.size();
    int len = 1;
    for (int i = 1; i < n; i++) {
        int idx = upper_bound(s.begin(), s.end(), a[i]) - s.begin();
        int m = s.size();
        if (m > idx) {
            s[idx] = a[i];
        } else {
            s.push_back(a[i]);
        }
    }
    return s.size();
}

- Suraj Garg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Anton · Accepted Answer

要找到最长的非严格递增子序列，请更改以下条件：

如果A[i]是所有活动列表中最小的结尾候选项，则我们将开始长度为1的新活动列表。
如果A[i]是所有活动列表中最大的结尾候选项，则我们将克隆最大的活动列表，并将其扩展A[i]。
如果A[i]在中间，则我们将找到一个具有小于A[i]的最大结束元素的列表。克隆并通过A[i]扩展此列表。我们将放弃与此修改列表长度相同的所有其他列表。

改为：

如果A[i]小于所有活动列表中最小的结尾候选项，则我们将开始长度为1的新活动列表。
如果A[i]是所有活动列表中最大的结尾候选项，则我们将克隆最大的活动列表，并将其扩展A[i]。
如果A[i]在中间，则我们将找到一个具有小于等于A[i]的最大结束元素的列表。克隆并通过A[i]扩展此列表。我们将放弃与此修改列表长度相同的所有其他列表。

对于您的示例序列的第四步应该是： 10不小于10（最小元素）。我们找到最大的小于等于10的元素（即会是s[0]==10）。克隆并通过10扩展此列表。丢弃长度为2的现有列表。新的s变为{10 10}。