LeetCode Longest Increasing Subsequence

LeetCode Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?


给定一个数组,求最长上升子序列(Longest Increasing Subsequence, LIS)的长度。子序列可以是不连续的,和子串不一样。
此题有两种解法,一种O(n^2),另一种O(nlgn)
先来看O(n^2)。设length[i]表示到nums[i]时的LIS,那么此时已知了length[0,...,i-1],对于j\in[0,...,i-1],如果nums[i]>nums[j],则在i处的LIS至少是length[j]+1,因为可以在nums[j]后面接nums[i],构成LIS,所以在i处的LIS加一。我们尝试所有的j\in[0,...,i-1],找一个最大的length[j]+1赋给length[i]。
递推式如下:

length(i) =  max  { length(j) + 1 : if nums[j] < nums[i] }
           0≤j≤i-1

这种思路的代码如下,因为需要两层循环,所以时间复杂度为O(n^2)

class Solution {
public:
	int lengthOfLIS(vector<int>& nums) {
		int n = nums.size();
		if (n < 1)return 0;
		vector<int> length(n, 1);
		int ans = 1;
		for (int i = 1; i < n; ++i) {
			for (int j = 0; j < i; ++j) {
				if (nums[i] > nums[j]) {
					length[i] = max(length[i], length[j] + 1);
				}
			}
			ans = max(ans, length[i]);
		}
		return ans;
	}
};

本代码提交AC,用时33MS。
接下来看看O(nlgn)的解法。
对于数组d(代码中的数组nums的简称),我们定义一个辅助数组B,B[j]保存了到目前为止LIS=j时的最后一个数的最小的数,比如B[3]=8表示到目前为止长度为3的上升子序列的最后一个数的最小值为8。我们不断更新B的长度和数值,最后B的长度就是最长的上升子序列的长度,但是数组B并不是一个LIS。
举例说明。假设数组下标从1开始。数组d=[3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12],初始时B的长度为1,且B[1]=3表明此时最长上升子序列的长度为1,且该LIS的最后一个数的最小值是3。
d[2]=5,因为d[2]>B[1],所以5可以加入最长上升子序列,导致此时的最长上升子序列长度为2,且最后一个数的最小值就是5,所以B[2]=5。此时B[1]=3不变,因为长度为1的LIS的末尾数值还是3不变。B=[3,5]
d[3]=6,同上,d[3]>B[2],所以6也加入最长上升子序列,导致LIS=3,且B[3]=6B=[3,5,6]
d[4]=2,注意此时d[4]<B[3],所以2不能增加以B[3]=6结尾的最长上升子序列,所以数组B的长度不变。查找B,发现2比B[1]=3小,所以替换B[1]=3为B[1]=2,此含义为长度为1的LIS的末尾最小数由3变更为2。这很好理解,因为2自身可以作为一个LIS,且比3自身作为LIS要小。B=[2,5,6]
d[5]=5,同上,d[5]<B[3],查找B,更新B[2]=5,因为B[2]本身就是5,所以更新前后一样。B=[2,5,6]
d[6]=4,d[6]<B[3],无法增长最长上升子序列,查找B,发现4在B[1]=2和B[3]=6之间,更新B[2]=4,含义为长度为2的LIS的最后一个数的最小值由5更新为4。B=[2,4,6]。其实这样更新的目的就是为了把各个长度的LIS的末尾的最小数变小,使得后续的数更有可能接在之前LIS的末尾来增加LIS的长度。
d[7]=19,d[7]>B[3],贡献LIS长度,直接加入数组B,即B[4]=19B=[2,4,6,19]
d[8]=5,查找B,在4,19之间,所以更新B[3]=5B=[2,4,5,19]
d[9]=6,查找B,更新B[4]=6B=[2,4,5,6]
d[10]=7,d[10]>B[4],贡献LIS长度,直接加入数组B,即B[5]=7B=[2,4,5,6,7]
d[11]=12,d[11]>B[5],贡献LIS长度,直接加入数组B,即B[6]=12B=[2,4,5,6,7,12]
以上算法过程涉及到在数组B中查找当前元素d[i]的替换位置,因为数组B是有序的,所以可以使用二分查找,最终算法的时间复杂度降为了O(nlgn)。
STL中自带了在有序数组中二分查找的函数,lower_bound输入为一个数组B和目标target,返回数组B中不小于target的最小下标。我们也可以自己用二分查找实现。
这种思路的代码如下:

class Solution {
public:
	int lowerbound(vector<int>& B, int target) {
		int l = 0, r = B.size() - 1;
		while (l < r) {
			int m = (l + r) / 2;
			if (B[m] == target)return m;
			else if (B[m] > target) r = m - 1;
			else l = m + 1;
		}
		return B[l] < target ? (l + 1) : l;
	}
	int lengthOfLIS(vector<int>& nums) {
		int n = nums.size();
		if (n < 1)return 0;
		vector<int> B = { nums[0] };
		for (int i = 1; i < n; ++i) {
			if (nums[i] > B.back())B.push_back(nums[i]);
			else {
				//*lower_bound(B.begin(), B.end(), nums[i]) = nums[i];
				B[lowerbound(B, nums[i])] = nums[i];
			}
		}
		return B.size();
	}
};

本代码提交AC,用时3MS,速度一下提高了不少。
参考:

2 thoughts on “LeetCode Longest Increasing Subsequence

  1. Pingback: LeetCode Largest Divisible Subset | bitJoy > code

  2. Pingback: LeetCode Maximum Length of Pair Chain | bitJoy > code

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.