O（nlgn）中最长的非递减子序列 [英] longest nondecreasing subsequence in O(nlgn)

问题描述

我有以下算法效果很好

我尝试在这里为自己解释 http://nemo.la/?p=943 ，并在此处进行了 http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ 等等同样，stackoverflow

I tried explaining it here for myself http://nemo.la/?p=943 and it is explained here http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/ as well and on stackoverflow as well

我想对其进行修改以产生最长的非单调递增子序列

I want to modify it to produce the longest non-monotonically increasing subsequence

30 20 20 10 10 10 10

for the sequence 30 20 20 10 10 10 10

答案应该是4： 10 10 10 10

the answer should be 4: "10 10 10 10"

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

But the with nlgn version of the algorithm it isn't working. Initializing s to contain the first element "30" and starting at the second element = 20. This is what happens:

1. The第一步：30不大于或等于20。我们找到大于20的最小元素。新s变为 20

1. The first step: 30 is not greater than or equal to 20. We find the smallest element greater than 20. The new s becomes "20"

第二步：20大于或等于20。我们扩展序列，并且s现在包含 20 20

The second step: 20 is greater than or equal to 20. We extend the sequence and s now contains "20 20"

第三步：10不大于或等于20。我们发现大于10的最小元素为 20。新的s变为 10 20

The third step: 10 is not greater than or equal to 20. We find the smallest element greater than 10 which is "20". The new s becomes "10 20"

，之后s将不再增长，算法将返回2而不是4

and s will never grow after that and the algorithm will return 2 instead of 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;
}

推荐答案

除了 binary_search（）函数中的问题，此函数应返回大于目标元素（x）的第一个元素的索引，因为您需要最长的非递减序列。对此进行修改，就可以了。

Your code nearly works except a problem in your binary_search() function, this function should return the index of the first element that's greater than the target element(x) since you want the longest non-decreasing sequence. Modify it to this, it'll be OK.

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

If you use c++, std::lower_bound() and std::upper_bound() will help you get rid of this confusing problem. By the way, the if statement"if (height[s[k]] >= height[i])" is superfluous.

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 */
}

这篇关于O（nlgn）中最长的非递减子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！