让我们先看一下n^2算法：
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
dp[i] = 1;
for( int j = 0; j < i; j++ ) {
if( array[i] > array[j] ) {
if( dp[i] < dp[j]+1 ) {
dp[i] = dp[j]+1;
}
}
}
}
现在的改进发生在第二个循环中，基本上，你可以通过使用二分搜索来提高速度。除了数组dp[]之外，我们还有另一个数组c[]，c非常特殊，c[i]表示：长度为i的最长递增序列的最后一个元素的最小值。
sz = 1;
c[1] = array[0]; /*at this point, the minimum value of the last element of the size 1 increasing sequence must be array[0]*/
dp[0] = 1;
for( int i = 1; i < len; i++ ) {
if( array[i] < c[1] ) {
c[1] = array[i]; /*you have to update the minimum value right now*/
dp[i] = 1;
}
else if( array[i] > c[sz] ) {
c[sz+1] = array[i];
dp[i] = sz+1;
sz++;
}
else {
int k = binary_search( c, sz, array[i] ); /*you want to find k so that c[k-1]<array[i]<c[k]*/
c[k] = array[i];
dp[i] = k;
}
}
6
sz 似乎是范围 [0:i) 中最长子序列的长度。 - ashen这是根据《编程竞赛指南》中的O(n*lg(n))解决方案（注意：此实现假设列表中没有重复项）：
set<int> st;
set<int>::iterator it;
st.clear();
for(i=0; i<n; i++) {
st.insert(array[i]);
it=st.find(array[i]);
it++;
if(it!=st.end()) st.erase(it);
}
cout<<st.size()<<endl;
为了应对重复项，可以检查数字是否已经在集合中。如果是，则忽略该数字，否则继续使用之前的方法。或者，可以反转操作顺序：首先删除，然后插入。下面的代码实现了这种行为：
set<int> st;
set<int>::iterator it;
st.clear();
for(int i=0; i<n; i++) {
it = st.lower_bound(a[i]);
if (it != st.end()) st.erase(it);
st.insert(a[i]);
}
cout<<st.size()<<endl;
第二个算法可以通过维护一个父数组，其中包含LIS中前一个元素在原始数组中的位置，来扩展以找到最长增序子序列（LIS）本身。
typedef pair<int, int> IndexValue;
struct IndexValueCompare{
inline bool operator() (const IndexValue &one, const IndexValue &another){
return one.second < another.second;
}
};
vector<int> LIS(const vector<int> &sequence){
vector<int> parent(sequence.size());
set<IndexValue, IndexValueCompare> s;
for(int i = 0; i < sequence.size(); ++i){
IndexValue iv(i, sequence[i]);
if(i == 0){
s.insert(iv);
continue;
}
auto index = s.lower_bound(iv);
if(index != s.end()){
if(sequence[i] < sequence[index->first]){
if(index != s.begin()) {
parent[i] = (--index)->first;
index++;
}
s.erase(index);
}
} else{
parent[i] = s.rbegin()->first;
}
s.insert(iv);
}
vector<int> result(s.size());
int index = s.rbegin()->first;
for(auto iter = s.rbegin(); iter != s.rend(); index = parent[index], ++iter){
result[distance(iter, s.rend()) - 1] = sequence[index];
}
return result;
}
2
一般来说，我们有一组长度不同的活动列表。我们将元素A[i]添加到这些列表中。我们按照它们的长度递减的顺序扫描列表（以找到最后一个元素）。我们将验证所有列表的末尾元素，以查找其末尾元素小于A[i]（即floor值）的列表。
我们的策略由以下条件确定， 1. 如果A[i]是所有活动列表中最小的末尾候选元素，则我们将开始长度为1的新活动列表。 2. 如果A[i]是所有活动列表中最大的末尾候选元素，则我们将克隆最大的活动列表，并将其扩展到A[i]。 3. 如果A[i]介于两者之间，则我们将找到具有小于A[i]的最大末尾元素的列表。克隆并通过A[i]扩展此列表。我们将放弃与此修改列表长度相同的所有其他列表。
请注意，在构建活动列表的任何实例中，以下条件得到维护。
“较小列表的末尾元素小于较大列表的末尾元素”。
通过一个例子来说明会更加清晰，让我们以维基百科的例子为例：
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}。
A[0] = 0。情况1：没有活动列表，创建一个。
0。
-----------------------------------------------------------------------------
A[1] = 8。情况2：克隆并扩展。
0。
0、8。
-----------------------------------------------------------------------------
A[2] = 4。情况3：克隆、扩展和丢弃。
0。
0、4。
0、8。已丢弃
-----------------------------------------------------------------------------
A[3] = 12。情况2：克隆并扩展。
0。
0、4。
0、4、12。
-----------------------------------------------------------------------------
A[4] = 2。情况3：克隆、扩展和丢弃。
0。
0、2。
0、4。已丢弃。
0、4、12。
-----------------------------------------------------------------------------
A[5] = 10。情况3：克隆、扩展和丢弃。
0。
0、2。
0、2、10。
0、4、12。已丢弃。
-----------------------------------------------------------------------------
A[6] = 6。情况3：克隆、扩展和丢弃。
0。
0、2。
0、2、6。
0、2、10。已丢弃。
-----------------------------------------------------------------------------
A[7] = 14。情况2：克隆并扩展。
0。
0、2。
0、2、6。
0、2、6、14。
-----------------------------------------------------------------------------
A[8] = 1。情况3：克隆、扩展和丢弃。
0。
0、1。
0、2。已丢弃。
0、2、6。
0、2、6、14。
-----------------------------------------------------------------------------
A[9] = 9。情况3：克隆、扩展和丢弃。
0。
0、1。
0、2、6。
0、2、6、9。
0、2、6、14。已丢弃。
-----------------------------------------------------------------------------
A[10] = 5。情况3：克隆、扩展和丢弃。
0。
0、1。
0、1、5。
0、2、6。已丢弃。
0、2、6、9。
-----------------------------------------------------------------------------
A[11] = 13。情况2：克隆并扩展。
0。
0、1。
0、1、5。
0、2、6、9。
0、2、6、9、13。
-----------------------------------------------------------------------------
A[12] = 3。情况3：克隆、扩展和丢弃。
0。
0、1。
0、1、3。
0、1、5。已丢弃。
0、2、6、9。
0、2、6、9、13。
-----------------------------------------------------------------------------
A[13] = 11。情况3：克隆、扩展和丢弃。
0。
0、1。
0、1、3。
0、2、6、9。
0、2、6、9、11。
0、2、6、9、13。已丢弃。
-----------------------------------------------------------------------------
A[14] = 7。情况3：克隆、扩展和丢弃。
0。
0、1。
0、1、3。
0、1、3、7
同时，确保我们已经保持了这个条件：“较小列表的末尾元素小于较大列表的末尾元素”。
这个算法被称为耐心排序。
http://en.wikipedia.org/wiki/Patience_sorting
所以，从一副牌中选择一个花色。找到洗牌后花色中最长的递增子序列。你永远不会忘记这种方法。
复杂度：O（NlogN）
来源：http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
2
现在，在阅读耐心排序之后，我重写了算法。我还编写了已更正的二分查找。
耐心排序类似于插入排序
与插入排序一样，耐心排序通过执行二分查找来找到下一个项的适当位置。二分查找是在按排序顺序构建的卡牌堆上完成的。让我为卡牌堆分配一个变量。（我说的是纸牌，因为耐心是一个简化的纸牌游戏）。//! card piles contain pile of cards, nth pile contains n cards.
int top_card_list[n+1];
for(int i = 0; i <= n; i++) {
top_card_list[i] = -1;
}
现在，
top_card_list 包含高度为 n 的牌堆中的顶部牌。耐心排序将手中的牌放在比它小（或相反）的最高顶部牌上。有关进一步排序的注意事项，请参阅维基百科页面上的“耐心排序”。 3
* 7 2
-------------------------------------------------------------
Pile of cards above (top card is larger than lower cards)
(note that pile of card represents longest increasing subsequence too !)
在一堆卡牌中进行二分查找
现在，在我们为最长递增子序列进行动态规划时，要查找一个数字，我们运行一个内部循环，其时间复杂度为O(n)。
for(int i = 1; i < n; i++) { // outer loop
for(int j = 0; j < i; j++) { // inner loop
if(arr[i] > arr[j]) {
if(memo_len[i] < (memo_len[j]+1)) {
// relaxation
memo_len[i] = memo_len[j]+1;
result = std::max(result,memo_len[i]);
pred[i] = j;
}
}
}
}
内循环的目的是找到手中卡牌小于最高顶部卡牌的卡牌。
但我们知道可以通过二分搜索来完成！（练习：证明正确性）这样，我们可以在O(log（堆数）)时间内完成。现在O(堆数)=O(卡牌数)（但卡牌数为52，应该是O（1）！开个玩笑！）。因此，整个应用程序运行时间为O(n log n)。
以下是使用二分搜索进行修订的DP。
for(int i = 1; i < n; i++) {
pile_height[i] = 1;
const int j = pile_search(top_card_list, arr, pile_len, arr[i]);
if(arr[i] > arr[j]) {
if(pile_height[i] < (pile_height[j]+1)) {
// relaxation
pile_height[i] = pile_height[j]+1;
result = std::max(result,pile_height[i]);
pile_len = std::max(pile_len,pile_height[i]);
}
}
if(-1 == top_card_list[pile_height[i]] || arr[top_card_list[pile_height[i]]] > arr[i]) {
top_card_list[pile_height[i]] = i; // top card on the pile is now i
}
}
以下是正确的堆搜索。它只是一个二分搜索，但它可以找到手中卡牌小于顶部卡牌索引。
inline static int pile_search(const int*top_card_list, const vector<int>& arr, int pile_len, int strict_upper_limit) {
int start = 1,bound=pile_len;
while(start < bound) {
if(arr[top_card_list[bound]] < strict_upper_limit) {
return top_card_list[bound];
}
int mid = (start+bound)/2 + ((start+bound)&1);
if(arr[top_card_list[mid]] >= strict_upper_limit) {
// go lower
bound = mid-1;
} else {
start = mid;
}
}
return top_card_list[bound];
}
请注意，与维基百科不同，它返回
top_card_list [bound]（我的修复）。 还要注意top_card_list []在dp中更新的位置。 该代码已经过边界情况的测试。 希望能对您有所帮助。set<int> my_set;
set<int>::iterator it;
vector <int> out;
out.clear();
my_set.clear();
for(int i = 1; i <= n; i++) {
my_set.insert(a[i]);
it = my_set.find(a[i]);
it++;
if(it != my_set.end())
st.erase(it);
else
out.push_back(*it);
}
cout<< out.size();
这里有一个证明https://strncat.github.io/jekyll/update/2019/06/25/longest-increasing-subsequence.html，基本上不可能不是严格递增的子序列。 证明采用反证法：假设不是，则有两种情况： 情况1）存在某个元素M[j]，它结束了长度为j和j+某个数字的两个子序列。这是不可能的（证明在链接中）。 情况2）与情况1略有不同，但推理基本相同。如何能使最小的数字结束两个不同长度的子序列？这是不可能的。
- 在已知的最后元素序列中找到直接前任（假设它的长度为
k） - 尝试将当前元素附加到此序列中，并为
k+1长度构建新的更好解决方案
k+1）将具有大于较短序列的最后一个元素。希望这能帮助到您。
你可以观看这个视频来了解：
https://www.youtube.com/watch?v=nf3YG4CnTbg&feature=youtu.be
我用nlogn方法的代码如下：
int n;
cin>>n;//LENGTH OF ARRAY
vector<int>v(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
vector<int>d(n+1,INT_MAX);//AUXILLARY ARRAY
for(int i=0;i<=n;i++){
*lower_bound(d.begin(),d.end(),v[i])=v[i];
}
for(int i=0;i<n;i++){
if(d[i]==INT_MAX){
cout<<i;//LENGTH OF LIS
exit(0);
}
}
原文链接