O(nlgn) 中的最长非减子序列

Question

我有以下运行良好的算法

我尝试在这里为自己解释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;
}

Answer 1

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

1. 如果A[i]是活动列表的所有最终候选者中最小的，我们将开始长度为 的新活动列表1。
2. 如果A[i]是活动列表的所有最终候选者中最大的，我们将克隆最大的活动列表，并将其扩展A[i]。
3. 如果A[i]介于两者之间，我们将找到一个列表，其最大结束元素小于A[i]。克隆并扩展此列表A[i]。我们将丢弃与此修改后的列表长度相同的所有其他列表。

到：

1. 如果A[i]小于活动列表所有最终候选者中最小的一个1，我们将开始长度为 的新活动列表。
2. 如果A[i]是活动列表的所有最终候选者中最大的，我们将克隆最大的活动列表，并将其扩展A[i]。
3. 如果A[i]介于两者之间，我们将找到一个最大结束元素小于或等于 的 A[i]列表。克隆并扩展此列表A[i]。我们将丢弃与此修改后的列表长度相同的所有其他列表。

示例序列的第四步应该是：

10不小于10（最小元素）。我们找到小于或等于10（即s[0]==10）的最大元素。克隆并扩展此列表10。丢弃长度为 2 的现有列表。新的列表s变为{10 10}。

Answer 2

除了函数中的问题之外，您的代码几乎可以工作binary_search()，该函数应该返回大于目标元素（x）的第一个元素的索引，因为您想要最长的非递减序列。修改成这样就OK了。

如果你使用c++，std::lower_bound()将会std::upper_bound()帮助你摆脱这个令人困惑的问题。顺便说一句，if语句“ 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 */
}

Answer 3

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