题目

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?

动态规划

[10, 9, 2, 5, 3, 7, 101, 18]为例，从最末尾的18开始，当只有一个元素时，长度等于1.

Sub(18)     = [18]                    = 1
Sub(101)    = [101,18]                = 1
Sub(7)      = [7,101,18]              = Max(Sub(18),Sub(101)) + 1 = 2
Sub(3)      = [3,7,101,18]            = Max(Sub(18),Sub(101),Sub(7)) + 1 = 3
...
...


T(n)等于[T(0)~T(n-1)]中所有 nums[k] > nums[n] 的子问题的最大值+1。

代码

class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) { return 0; }
int[] dp = new int[nums.length];
dp[nums.length-1] = 1;
int max = 1;
for (int i = nums.length-2; i >= 0; i--) {
dp[i] = 1;
for (int j = i+1; j < nums.length; j++) {
if (nums[j] > nums[i]) { dp[i] = Math.max(dp[i],dp[j]+1); }
}
max = Math.max(max,dp[i]);
}
return max;
}
}


用二分查找维护一个“最小尾数”数组

“最小尾数”数组就是让升序序列中的每一个数都尽可能地小。当新加入一个数，如果这个数能扩展最长升序路径的话，这个扩展在最小尾数数组上一定可行。

• 如果新加入的数大于当前“最小尾数”数组最后一个数，就把新的数插入到“最小尾数”数组的末尾。
• 如果新加入的数介于“最小尾数”数组覆盖的范围内，则更新数组内大于它的最小的那个数字。

[10]                    -> 插入末尾: [10]
[10,9]                  -> 更新10: [9]
[10,9,2]                -> 更新9: [2]
[10,9,2,5]              -> 插入末尾: [2,5]
[10,9,2,5,3]            -> 更新5: [2,3]
[10,9,2,5,3,7]          -> 插入末尾: [2,3,7]
[10,9,2,5,3,7,101]      -> 插入末尾: [2,3,7,101]
[10,9,2,5,3,7,101,18]   -> 更新101: [2,3,7,18]


代码

class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int cur = 0;
for (int num : nums) {
int lo = 0, hi = cur - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (tails[mid] < num) {
lo = mid + 1;
} else if (tails[mid] > num) {
hi = mid - 1;
} else {
lo = mid; break;
}
}
if (lo == cur) {
tails[cur++] = num;
} else {
tails[lo] = num;
}
}
return cur;
}
}