题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
题解
思路1:动态规划
定义dp[i]为以i元素结尾的最长递增子序列的长度
我们从小到大计算dp数组的值，在计算dp[i]之前，我们已经计算出dp[0…i−1] 的值，则状态转移方程为
dp[i] = max(dp[j]) + 1 (0<=j<i 且 num[i]>nums[j])
边界条件：dp[0] = 1
// OC
+ (int)lengthOfLIS1:(NSArray *)nums {
int n = (int)nums.count;
int dp[n];
dp[0] = 1;
int res = 1;
for (int i=1; i<n; i++) {
int tempLen = 1;
for (int j=0; j<i; j++) {
if ([nums[i] intValue] > [nums[j] intValue]) {
tempLen = MAX(tempLen, dp[j]+1);
}
}
dp[i] = tempLen;
if (dp[i] > res) {
res = dp[i];
}
}
return res;
}
// Swift
static public func lengthOfLIS1(_ nums:[Int]) -> Int {
let n = nums.count
var dp = Array(repeating: 1, count: n)
var res = 1
for i in 1..<n {
for j in 0..<i {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j] + 1)
}
}
if res < dp[i] {
res = dp[i]
}
}
return res
}
思路2:贪心算法+二分法查找
想获得最长递增子序列，我们需要让递增子序列上升得尽可能的慢，也就是说每次在递增子序列最后加上的那个数尽可能的小
定义dp[len]为长度为len的递增子序列末尾最小元素，边界条件：dp[1] = nums[0]
d[len]是关于len单调递增的
对于任意长度为i的递增子序列(末尾元素为x)，我们在末尾删除一个元素，都可以得到一个长度为i-1的递增子序列(末尾元素为y),很明显y<x。
dp[i] 表示长度为i的递增子序列的最小元素，即dp[i] = min(x0,x1,x2...),dp[i-1] 表示长度为i-1的递增子序列的最小元素，即dp[j] = min(y0,y1,y2...),又由于x0>y0,x1>y1,...,则dp[i]>dp[i-1]
因而d[len]是关于len单调递增的。
我们从小遍历数组nums，比较nums[i]和dp[len],更新len和dp[len]
如果nums[i] > dp[len],表示当前长度len的递增子序列的末尾元素小于nums[i],则len=len+1,dp[len] = nums[i];
如果nums[i] < dp[len],则在dp数组中查找，找到一个k(0<k<=len)，dp[k-1]<nums[i]<dp[k],更新dp[k] = nums[i],如果找不到k，则说明所有dpj都比nums[i],则更新dp[0] = nums[i]
在nums[i] < dp[len]，查找k的过程中，由于dp是单调递增的，我们可以通过二分法查找，即查找第一个比nums[i]小的数d[k],更新d[k+1]=nums[i]
// OC
+ (int)lengthOfLIS2:(NSArray *)nums {
int n = (int)nums.count;
if (n<=1) {
return n;
}
// dp[len]为长度为len的递增子序列末尾最小元素，边界条件：dp[1] = nums[0]
int dp[n];
dp[1] = [nums[0] intValue];
int len = 1;
for (int i=1; i<n; i++) {
if ([nums[i] intValue] > dp[len]) {
len ++;
dp[len] = [nums[i] intValue];
}else{
int left = 1;
int right = len;
int pos = 0;
// 二分法查找第一个小于nums[i]的k
while (left <= right) {
int mid = (left+right)/2;
if ([nums[mid] intValue] < [nums[i] intValue]) {
pos = mid;
left = mid+1;
}else{
right = mid-1;
}
}
dp[pos+1] = [nums[i] intValue];
}
}
return len;
}
// Swift
static public func lengthOfLIS2(_ nums:[Int]) -> Int {
if nums.count <= 1 {return nums.count}
let n = nums.count
var dp = Array(repeating: -1, count: n+1)
var len = 1
dp[1] = nums[0]
for i in 1..<n {
if nums[i] > dp[len] {
len += 1
dp[len] = nums[i]
}else{
var l=1
var r=len
var pos = 0
while l<=r {
let mid = (l+r)/2
if dp[mid] < nums[i] {
pos = mid
l = mid+1
}else{
r = mid-1
}
}
dp[pos+1] = nums[i]
}
}
return len
}
参考：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xwhvq3/
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/
