最长不降子序列的一些总结

Posted on | In | | Visitors:
Words count in article: 2.4k

最长不降子序列的一些总结

算法课上讲到了最长不降子序列以及一系列变种，虽然老师轻轻松松花了30分钟就讲完了，但是真要自己课后一个一个写一遍发现事情并不简单…

1. 最长不降子序列

leetcode原题链接：300. 最长上升子序列

题目描述：给定一个无序的整数数组，找到其中最长上升子序列的长度。

举个栗子：输入[10,9,2,5,3,7,101,18]，则最长上升子序列为[2,3,7,101]，所以输出4

题目非常经典，也比较好懂，记录一下两种解法

解法1：动态规划

定义 dp[i] 为前 i 个元素，以第 i 个数字结尾的最长上升子序列长度，于是我们就能写出状态转移方程：

有了状态方程就能开心的开始写代码了^_^（懒得自己写了，代码采用leetcode官方解答）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=(int)nums.size();
        if (n == 0) return 0;
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

由于每次计算 dp[i] 都需要对 i 之前的元素进行计算，所以时间复杂度为 $O(n^2)$ 。

解法2：贪心+二分查找

定义 arr[i] 表示长度为 i 的上升子序列末尾元素的最小值，用length记录当前的最长上升子序列长度。

然后我们就只需遍历输入数组nums的每个元素，该元素比末尾元素arr[length]还要大，则增大序列长度并记录该元素（arr[++length] = nums[i]），否则就在arr的length个元素中找到第一个大于num[i]的元素，并且更新该元素。

显然 arr[i] 是单调递增的，于是当我们需要更新arr时就能用到二分查找，优化了时间复杂度。下面时具体代码实现

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
class Solution {
public:
int arr[5000] = { 0 }, length = 0;
void insert(int num, int from, int to) {
	int center;
	while (from != to) {
		center = (from + to) / 2;
		if (arr[center] < num) {
			from = center + 1;
		}
		else {
			to = center;
		}
	}
	arr[from] = num;
}
int lengthOfLIS(vector<int>& nums) {
	if (nums.empty())
		return 0;
	arr[0] = nums[0];
	for (auto num : nums) {
		if (num > arr[length]) {
			arr[length + 1] = num;
			length++;
		}
		else {
			insert(num, 0, length);
		}
	}
	return length + 1;
}
};

对于二分查找其实可以直接调用STL库函数 lower_bound() 和 upper_bound() （只能在有序数组或者容器中使用，内部其实就是二分查找实现的）

可以参考C++ STL详细笔记

2. 拦截导弹

洛谷原题链接

题目描述：某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

举个栗子：输入为：389 207 155 300 299 170 158 65

则最长不升子序列为：389 300 299 170 158 65，所以最多能拦截6枚导弹，还有一个不升子序列为：207 155，所以共需要2套这种导弹拦截系统。因此输出为 6 , 2

解答：

第一问就是一个最长不升子序列问题，和上题相同，不再赘述

第二问其实特别巧妙，共需要多少套导弹拦截系统其实就是最长上升子序列的长度（因为上升子序列的任意两个元素都不可能在一个不升子序列中）

理解清晰后，这题就能秒杀了，就是两个最长升/降序子序列问题。（但是需要注意等号是否成立，细细体会上升与不降，或者下降与不升的代码的微妙差别^_^）

那就放代码吧：

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
#include<iostream>
#include<algorithm>
using namespace std;
int Arr1[100000] = { 0 }, length1 = 0, Arr2[100000] = { 0 }, length2 = 0;
void missileInterception(int inputArr[], int size) {
	
	int* p;
	if (size == 0)
		cout << 0 << endl << 0 << endl;
	Arr1[0] = inputArr[0];	// 不升序列
	Arr2[0] = inputArr[0];	// 下降序列
	for (int i = 1; i < size; i++) {
		if (Arr1[length1] >= inputArr[i]) {
			Arr1[++length1] = inputArr[i];
		}
		else {
			p = upper_bound(Arr1, Arr1 + length1 + 1, inputArr[i], greater<int>());
			*p = inputArr[i];
		}
		if (Arr2[length2] < inputArr[i]) {
			Arr2[++length2] = inputArr[i];
		}
		else {
			p = lower_bound(Arr2, Arr2 + length2 + 1, inputArr[i]);
			*p = inputArr[i];
		}
	}
	cout << length1 + 1 << endl << length2 + 1 << endl;
}
int main()
{
	int inputArr[100000] = { 0 };
	int i = 0;
	while (cin >> inputArr[i]) {
		i++;
	}
	missileInterception(inputArr, i);
	return 0;
}

3. 低价购买

洛谷原题链接

题目描述：“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价( $2^{16}$ 范围内的正整数)，你可以选择在哪些天购买这支股票。每次购买都必须遵循“低价购买；再低价购买”的原则。写一个程序计算最大购买次数。

这里是某支股票的价格清单：

日期 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8, 9 ,10 ,11, 12

价格68 ,69 ,54, 64,68 ,64 ,70 ,67 ,78 ,62, 98, 87

最优秀的投资者可以购买最多4次股票，可行方案中的一种是：

日期 2 , 5 , 6 ,10

价格 69, 68 ,64 ,62

现在我们需要求解最大购买次数以及最大购买次数的方案数（如果构成的价格队列一样的时视为一种方案）

上述提到的样例输出应为：4, 2

解答：

第一问仍然是一个求解最长下降子序列长度的问题，同上。

而第二问需要求解对应的方案数，其实思路和最长不降子序列动态规划解法思路相同，只是用 dp[i] 表示相应的方案数而已， 也是由前面元素 dp[j] 推得，记得进行去重操作即可。

看代码吧：

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
#include<iostream>
#include<algorithm>
using namespace std;
int lengthArr[5100] = { 0 }, wayArr[5100] = { 0 };
void buyInLowPrice(int inputArr[], int size) {
	int temp, maxLength = 0, wayCount = 0;
	for (int i = 0; i < size; i++) {
		temp = 1;
		for (int j = 0; j < i; j++) {
			if (inputArr[j] > inputArr[i]) {
				temp = max(temp, lengthArr[j] + 1);		// 求最长下降子序列长度
			}
		}
		maxLength = max(temp, maxLength);
		lengthArr[i] = temp;
		for (int j = 0; j < i; j++) {
			if (inputArr[j] == inputArr[i] && lengthArr[i] == lengthArr[j]) {
				wayArr[j] = 0;		// 方案去重，如果价格相同并且序列长度也相同，则方案一定相同
			}
			if (inputArr[j] > inputArr[i] && lengthArr[i] == lengthArr[j] + 1) {
				wayArr[i] += wayArr[j];		// 加上所有的子方案数
			}
		}
		wayArr[i] = (wayArr[i] == 0 ? 1 : wayArr[i]);
	}
	for (int i = 0; i < size; i++) {
		if (lengthArr[i] == maxLength)
			wayCount += wayArr[i];		// 计算所有序列长度为maxLength的方案数总和
	}
	cout << maxLength << " " << wayCount << endl;
}
int main()
{
	int inputArr[5100], n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> inputArr[i];
	}
	buyInLowPrice(inputArr, n);
	return 0;
}

4. 合唱队形

洛谷原题链接

题目描述：

06Dw1H.png

题目很好懂，就不举栗子了~

解答：

可能乍一看并没有发现可以用最长不降子序列的思路来解题~

假设我们选取第 i 位同学作为分界线，然后在 i 左侧求解最长上升子序列，在 i 右侧求解最长下降子序列，队伍总人数减去这两个子序列长度便是需要出列同学的个数了~

我们就只需要穷举第 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
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int arr1[110] = { 0 }, arr2[110] = { 0 }, length1 = 0, length2 = 0;
int popNum(int inputArr[], int center, int n) {
	int popCount = 0;
	int* p;
	memset(arr1, 0, sizeof(arr1));
	memset(arr2, 0, sizeof(arr2));
	length1 = 0;
	length2 = 0;
	arr1[0] = inputArr[0];
	for (int i = 1; i <= center; i++) {
		if (inputArr[i] > arr1[length1]) {
			arr1[++length1] = inputArr[i];
		}
		else {
			p = lower_bound(arr1, arr1 + length1 + 1, inputArr[i]);
			*p = inputArr[i];
		}
	}
	popCount += (center - length1);

	arr2[0] = inputArr[center];
	for (int i = center + 1; i < n; i++) {
		if (inputArr[i] < arr2[length2]) {
			arr2[++length2] = inputArr[i];
		}
		else {
			p = lower_bound(arr2, arr2 + length2 + 1, inputArr[i], greater<int>());
			*p = inputArr[i];
		}
	}
	popCount += (n - center - 1 - length2);
	return popCount;
}
int main()
{
	int inputArr[110], n, count;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> inputArr[i];
	}
	count = n;
	for (int i = 0; i < n; i++) {
		count = min(popNum(inputArr, i, n), count);
	}
	cout << count << endl;
	return 0;
}

唉，动态规划好难鸭T_T