6

我有以下算法，效果很好

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

6 回答 6

5

除了函数中的问题外，您的代码几乎可以工作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 */
}
于 2014-02-12T03:31:57.887 回答
5

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

  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}。

于 2014-02-12T01:15:10.873 回答
4

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

于 2014-02-12T04:21:24.887 回答
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;
}
于 2019-04-25T10:13:56.950 回答
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。

希望这可以帮助！

于 2014-02-12T03:25:03.420 回答
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();
}
于 2022-01-25T13:18:51.397 回答