给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
https://leetcode-cn.com/problems/longest-increasing-subsequence
动态规划
时间复杂度为 O(n2)，
维护一个一维 dp 数组，其中 dp[i] 表示以 nums[i] 为结尾的最长递增子串的长度，
对于每一个 nums[i]，从第一个数再搜索到i，如果发现某个数小于 nums[i]，更新 dp[i]，
更新方法为 dp[i] = max(dp[i], dp[j] + 1)，即比较当前 dp[i] 的值和那个小于 num[i] 的数的 dp 值加1的大小，就这样不断的更新 dp 数组，到最后 dp 数组中最大的值就是我们要返回的 LIS 的长度，参见代码如下：
c++
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};
java
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j])
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
python
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums: return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
二分查找
优化时间复杂度到 O(nlgn) ，这里用到了二分查找法。
思路是，先建立一个数组 ends，把首元素放进去，然后比较之后的元素，如果遍历到的新元素比 ends 数组中的首元素小的话，替换首元素为此新元素，
如果遍历到的新元素比 ends 数组中的末尾元素还大的话，将此新元素添加到 ends 数组末尾(注意不覆盖原末尾元素)。
如果遍历到的新元素比 ends 数组首元素大，比尾元素小时，此时用二分查找法找到第一个不小于此新元素的位置，覆盖掉位置的原来的数字，以此类推直至遍历完整个 nums 数组，
此时 ends 数组的长度就是要求的LIS的长度，特别注意的是 ends 数组的值可能不是一个真实的 LIS，比如若输入数组 nums 为 {4，2，4，5，3，7}，那么算完后的 ends 数组为 {2，3，5，7}，可以发现它不是一个原数组的 LIS，只是长度相等而已，千万要注意这点。参见代码如下：
c++
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.empty()) return 0;
vector<int> ends{nums[0]};
for (auto a : nums) {
if (a < ends[0]) ends[0] = a;
else if (a > ends.back()) ends.push_back(a);
else {
int left = 0, right = ends.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (ends[mid] < a) left = mid + 1;
else right = mid;
}
ends[right] = a;
}
}
return ends.size();
}
};
动态规划+二分查找
思路是先建立一个空的 dp 数组，然后开始遍历原数组，对于每一个遍历到的数字，用二分查找法在 dp 数组找第一个不小于它的数字，如果这个数字不存在，那么直接在 dp 数组后面加上遍历到的数字，
如果存在，则将这个数字更新为当前遍历到的数字，最后返回 dp 数组的长度即可，注意的是，跟上面的方法一样，特别注意的是 dp 数组的值可能不是一个真实的 LIS。参见代码如下：
c++
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp;
for (int i = 0; i < nums.size(); ++i) {
int left = 0, right = dp.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (dp[mid] < nums[i]) left = mid + 1;
else right = mid;
}
if (right >= dp.size()) dp.push_back(nums[i]);
else dp[right] = nums[i];
}
return dp.size();
}
};
java
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int res = 0;
for(int num : nums) {
int left = 0, right = res;
while(left < right) {
int m = (left + right) / 2;
if(dp[m] < num) left = m + 1;
else j = m;
}
dp[left] = num;
if(res == right) res++;
}
return res;
}
}
python
class Solution:
def lengthOfLIS(self, nums: [int]) -> int:
dp, res = [0] * len(nums), 0
for num in nums:
left, right = 0, res
while left < right:
m = (left + right) // 2
if dp[m] < num: i = m + 1
else: right = m
dp[left] = num
if right == res: res += 1
return res