最长递增子序列-LIS

LIS问题(Longest Increasing Subsequence Problem) 动态规划中经典的问题

简单来讲就是要找到一个序列中,所有递增子序列中长度最长的子序列的长度。子序列的取值不要求在原序列中连续。

动态规划

dp[i] 记录: 以arr[i]结尾的递增子序列的最大长度。
dp[i] 的更新:遍历 arr[0] 到 arr[i - 1] 中 小于 arr[i] 的数,并找到所有满足条件的arr[x] 中 dp[x] 最大的那个dp[n],则dp[i] = dp[n] + 1
参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// lis 动态规划 复杂度 O(n^2)
int lis(int *arr, int length)
{

const int len = length;
int dp[len] = {0};
int tmpMax = 0;
for(int i = 0; i < length; ++i)
{
tmpMax = 0;
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j])
tmpMax = max(dp[j],tmpMax);
}
dp[i] = tmpMax + 1;
}

tmpMax = 0;
for(int i = 0; i < length; ++i)
{
if(dp[i] > tmpMax)
{
tmpMax = dp[i];
}
}
return tmpMax;

}

另一种递增,即必须严格递增,不能相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 严格递增不能相等lis
void lis(vector<int> &arr, vector<int> &dp)
{
const int len = arr.size();
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
}

动态规划 + 二分

dp[i] 记录:当前最长的递增子序列的值
dp[i] 更新:把arr[i] 放入到 dp[i] 中,其放置方法为,从arr[0] 到 arr[len] 找到第一个大于等于arr[i]的位置pos,dp[pos] = arr[i]。并更新len = max(len,pos+1);
len增加(len < pos +1)的情况只有一种,便是在当前序列的末尾增加了一个数(pos = len),反之如果只是在中间进行替换并不会改变len的大小。
注意到这里对 pos 的查找是对一个有序的序列的查找,可以使用二分查到达到log(n) 的复杂度。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 二分+动态规划
lisDich(int *arr, int length)
{
const int l = length;
int dp[l] = {0};
dp[0] = arr[0];
int len = 1;
for(int i = 1; i < length; ++i)
{
int pos = lower_bound(dp,dp+len,arr[i]) - dp;//二分查找,节省时间
dp[pos] = arr[i];
len = max(len,pos+1);
}
return len;
}

这里用到的函数函数lower_bound() 用于在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置

华为机试题 24题 合唱队

一种LIS的变种,通过正向与反向两次dp得到arr[i]左侧递增和右侧递减的长度,将两者相加得到一个满足条件的最大长度。
示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void lis(vector<int> &arr, vector<int> &dp)
{
const int len = arr.size();
for(int i = 0; i < len; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
}

int calLis(vector<int> &arr)
{
const int size = arr.size();
vector<int> dpf(size,1);
vector<int> dpr(size,1);
vector<int> dp(size,1);
lis(arr,dpf);
reverse(arr.begin(),arr.end());
lis(arr,dpr);
reverse(dpr.begin(),dpr.end());

int max = 0;
for(int i = 0; i < size; ++i)
{
dp[i] = dpf[i] + dpr[i];
if(max < dp[i])
max = dp[i];
}

return max - 1;
}

int main(int argc, char *argv[])
{
int count = 0;
vector<int > arr;
while(cin>>count)
{
int tmp;
arr.clear();
while(count-- > 0)
{
cin>>tmp;
arr.push_back(tmp);
}

int len = arr.size() - calLis(arr);
cout<<len<<endl;
}

return 0;
}

T B
站点访问量: / , 本页阅读量:
T B