hid*_*boy 77
我们先来看看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;
}
}
Har*_*rla 24
这是来自The Hitchhiker的编程竞赛指南的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;
}
She*_*mar 10
我们需要维护增加序列的列表.
通常,我们有一组不同长度的活动列表.我们在这些列表中添加了元素A [i].我们按照长度的降序扫描列表(对于最终元素).我们将验证所有列表的结束元素,以找到其结束元素小于A [i](底值)的列表.
我们的策略由以下条件确定:
1.如果A [i]在活动列表的所有最终候选者中最小,我们将启动长度为1的新活动列表
.2.如果A [i]在所有活动的最终候选者中最大列表,我们将克隆最大的活动列表,并通过A [i]扩展它.
3.如果A [i]介于两者之间,我们将找到一个最大结束元素小于A [i]的列表.通过A [i]克隆并扩展此列表.我们将丢弃与此修改列表长度相同的所有其他列表.
请注意,在构建活动列表期间的任何实例中,都会保持以下条件.
"较小列表的结束元素小于较大列表的结尾元素".
通过一个例子可以清楚地看到,让我们从wiki中获取示例:
{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,0,2,6,9,废弃.
0,2,6,9,11
.------------------------------------ ------------------------------------
A [15] = 15.案例2.克隆并延长.
0
0,1
0,1,3,
0,1,3,7,
0,2,6,9,11,
0,2,6,9,11,15 < - LIS列表
另外,确保我们保持条件,"较小列表的结尾元素小于较大列表的结尾元素".
该算法称为耐心排序.
http://en.wikipedia.org/wiki/Patience_sorting
所以,从一副牌中挑选一套西装.从洗牌的西装中找出增长最快的子牌序列.你永远不会忘记这种方法.
复杂性:O(NlogN)
资料来源:http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
算法背后的基本思想是保留给定长度的 LIS 列表，以最小可能元素结尾。构造这样的序列
k）k+1长度解决方案因为在第一步中，您搜索的值小于 X[i]，所以新的解决方案（对于k+1）将具有比更短的序列更大的最后一个元素。
我希望它会有所帮助。