LIS 老题目了，然而我忘了。。。

动态规划

直接 DP 问题不大，注意一下给你的如果是个空数组就行了

对于位置 i ，dp[i] 表示以 nums[i] 结尾的 LIS 的长度

所以初始化 dp[i]=1, 1<=i<=n 毕竟每个位置自身就是长度为1的 LIS

对于位置 i ，dp[i] 一定是由前面的结尾的值小于 nums[i] 的位置转移过来的

所以 dp[i]=max(dp[j]+1), 1<=j<i, a[j]<a[i]

O(n^2) 的时间， O(n) 的空间，最长不降子序列加等号就行

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)
	{
		vector<int> dp(nums.size(), 1);

		for (auto i = 0; i < nums.size(); i++)
			for (auto j = 0; j < i; j++)
				if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

		auto ans = 0;
		for (auto it : dp) ans = max(ans, it);

		return ans;
	}
};

二分查找优化

有一个题解是这样说的，道理是这个道理，然而我不知道为什么这样是对的：

新建数组 cell，用于保存最长上升子序列
对原序列进行遍历，将每位元素二分插入 cell 中
如果 cell 中元素都比它小，将它插到最后
否则，用它覆盖掉比它大的元素中最小的那个。
总之，思想就是让 cell 中存储比较小的元素。这样，cell 未必是真实的最长上升子序列，但长度是对的。

当然还有一个我能理解的办法，不然我也不会写这个东西了

这个办法的核心是维护一个数组，d[i] 表示长度为 i 的 LIS 的末尾元素的最小值，初始化 d[1]=nums[0] 。同时维护一个变量 len 标记目前的 LIS 长度.

遍历数组，对于每一个元素 nums[i]：

  • 如果这个元素大于已知的最长 LIS 的末尾元素，那么我们就找到了一个更长的 LIS ，因此 len++, d[len]=nums[i]
  • 否则二分查找数组 d ，找到第一个比 nums[i] 小的位置 j，j 就是这个元素前面能用的最大 LIS 长度，d[j+1] 肯定是大于nums[i] ，那么现在长度为 j+1 的 LIS 末尾元素最小值就应该是 nums[i]，d[j+1]=nums[i]

这样操作数组 d 肯定是单调的，所以可以用二分查找

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
class Solution
{
public:
	int lengthOfLIS(vector<int>& nums)
	{
		if (nums.empty()) return 0;

		vector<int> d(nums.size() + 1, 0);
		auto len = 1;
		d[1] = nums[0];

		for (auto it : nums)
		{
			if (it > d[len])
			{
				len++;
				d[len] = it;
			}
			else
			{
				const auto index = lower_bound(d.begin() + 1, d.begin() + 1 + len, it) - d.begin();
				d[index] = it;
			}
		}

		return len;
	}
};