2

我在一本书中找到了 LIS 的代码，但我不太能够证明正确性。有人可以帮我解决这个问题。如果新元素不是最大值，则所有代码都在删除集合中新插入元素旁边的元素，否则只插入新元素。

    set<int> s;
    set<int>::iterator it;
    for(int i=0;i<n;i++)
    {
         s.insert(arr[i]);
             it=s.find(arr[i]);
         it++; 
         if(it!=s.end()) 
           s.erase(it);
    }
    cout<<s.size()<<endl;

n 是序列的大小，arr 是序列。如果我们不必找到“严格”递增的序列，我认为以下代码不会起作用。我们能否修改代码以找到允许相等的递增序列。

编辑：该算法仅在输入不同时才有效。

4

4 回答 4

3

LIS 有多种解决方案。最典型的是使用动态编程的 O(N^2) 算法，其中对于每个索引 i 计算“以索引 i 结束的最长递增序列”。您可以使用巧妙的数据结构或二进制搜索将其加速到 O(N log N)。

您的代码绕过了这一点，只计算了 LIS 的长度。考虑输入“1 3 4 5 6 7 2”，最后集合的内容将是“1 2 4 5 6 7”，这不是LIS，但长度是正确的。证明应该使用归纳如下：

在第 i 次迭代之后，第 j 个最小元素是数组的前 i 个元素中长度为 j 的递增序列的最小可能端。

考虑输入“1 3 2”。在第二次迭代之后，我们设置了“1 3”，所以 1 是长度为 1 的递增序列的最小可能端，而 3 是长度为 2 的递增序列的最小可能端。
在第三次迭代之后，我们设置了“1 2”，现在2 是长度为 2 的递增序列的最小可能端。

我希望你可以自己做归纳步骤:)

于 2013-09-01T14:18:16.777 回答
2

该代码是 LIS 的 O(nlogn) 解决方案，但您想找到非严格递增的序列，实现存在问题，因为 std::set 不允许重复元素。这是有效的代码。

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int main()
{
    int arr[] = {4, 4, 5, 7, 6};
    int n = 5;
    multiset<int> s;
    multiset<int>::iterator it;
    for(int i=0;i<n;i++)
    {
        s.insert(arr[i]);
        it = upper_bound(s.begin(), s.end(), arr[i]);
        if(it!=s.end()) 
            s.erase(it);
    }
    cout<<s.size()<<endl;
    return 0;
}
于 2013-09-01T15:03:17.593 回答
2

证明相对简单：将集合s视为排序列表。我们可以用循环不变量来证明它。在算法的每次迭代之后，包含结束子数组中从零到我们目前考虑的最后一个元素的长度递增子序列s[k]的最小元素。我们可以通过归纳来证明这一点：arrkarr

  • 在第一次迭代之后，这个陈述是正确的，因为s将只包含一个元素，这是一个元素的平凡升序。
  • 每次迭代都可以通过以下两种方式之一更改集合：如果arr[i]是迄今为止找到的最大元素，它可以将集合扩展一，或者用 替换现有元素arr[i]，该元素小于之前存在的元素。

当集合的扩展发生时，它发生是因为当前元素arr[i]可以附加到当前 LIS。当替换发生在 positionk的索引处时arr[i]，它发生是因为arr[i]结束了 length 的升序子序列k，并且小于或等于s[i]用于结束前一个“最佳”升序 length 子序列的旧的k。

有了这个不变量，很容易看出它s包含的元素与arr整个arr耗尽后最长的升序子序列一样多。

于 2013-09-01T15:33:48.710 回答
-1

问题陈述：

  For A(n) :a0, a1,….an-1 we need to find LIS

  Find all elements in A(n) such that, ai<aj and i<j.
  For example: 10, 11, 12, 9, 8, 7, 5, 6
  LIS will be 10,11,12

这是基于 DP 的 O(N^2) 解决方案。

1 Finding SubProblems
Consider D(i): LIS of (a0 to ai) that includes ai as a part of LIS.
2 Recurrence Relation
D(i) = 1 + max(D(j) for all j<i) if ai > aj
3 Base Case
D(0) = 1;

查看代码链接： https ://innosamcodes.wordpress.com/2013/07/06/longest-increasing-subsequence/

于 2013-09-01T14:22:36.503 回答