DP O(n)遍历 + Binary Search = O(nlogn)

　　LeetCode 300. 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?

　　分析：
　　数组乱序，所以一次O(n)遍历所有元素是必需的。
　　找出其中最长的递增子序列。所以至少需要两个变量，一个表示递增，一个表示子序列长度。
　　假设序列长度为length，现在遍历到第 i 个元素。为了获得递增子序列，可以有几种方法：
　　法一：最初想到的是从该第 i 个元素向后遍历，看依次比它大的元素有多少，但是对于比他大的元素，如何选择哪一个元素作为子序列的第几个元素，会产生额外的时间复杂度。再记录子序列长度。这样最后就知道从每一个元素开始向后所得的递增子序列长度。只是复杂度达到O(n^3)。不可取。
　　法二：DP。从第 0 个元素遍历到第 i 个元素。另设一个数组dp[length]，存储从第 0 到第 i 个元素为止，以第 i 个元素为截止元素的最长递增子序列的长度。对于第 i 个元素，看其前面的元素值是否有比它小的，如果有，并且那个元素值的 (dp[]值 + 1) > dp[i]，则更新 dp[i] 值。这样最后单独再遍历一遍 dp[] 取最大值，就知道结果了。
　　Java代码如下。

public int lengthOfLIS(int[] nums) {
//O(n^2)
int l = nums.length;
if(l <= 1)
return l;
int[] dp = new int[l];
Arrays.fill(dp,1);
for(int i = 0; i<l; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]){
if(dp[j] + 1 > dp[i])
dp[i] = dp[j] + 1;
}
}
}
int res = dp[0];
for(int t : dp)
res = res > t ? res:t;
return res;
}

　　法三：DP + Binary Search
　　直接引用了他人的做法和思路：
　　1, traverse from 0 to len-1, the DP array keep the longest sequence.
　　2, if the val is bigger than largest in the dp array, add it to the end;
　　3, if it is among the sequence, return the pos that bigger than pres, update the array with this position if val is smaller than dp[pos];
　　This is to keep the sequence element with the smallest number.
　　
　　For example:

10, 9, 2, 5, 3, 7, 101, 18
10
9
2
2,5
2,3
2,3,7
2,3,7,101
2,3,7,18

　　Java代码如下。

public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];//由于可能存在多个最长递增子序列，所以dp可能存储递增最长子序列，也可能不一定。但不影响最长递增子序列的大小返回值
dp[0] = nums[0];
int len = 0;
for (int i = 1; i < nums.length; i++) {
int pos = binarySearch(dp,len,nums[i]);
if (nums[i] < dp[pos]) dp[pos] = nums[i];
if (pos > len) {
len = pos;
dp[len] = nums[i];
}
}
return len+1;
}
private int binarySearch(int[] dp, int len, int val) {
int left = 0;
int right = len;
while(left+1 < right) {
int mid = left + (right-left)/2;
if (dp[mid] == val) {
return mid;
} else {
if (dp[mid] < val) {
left = mid;
} else {
right = mid;
}
}
}
if (dp[right] < val) return len+1;
else if (dp[left] >= val) return left;
else return right;
}
}

最后

以上就是美丽马里奥为你收集整理的DP O(n)遍历 + Binary Search = O(nlogn)的全部内容，希望文章能够帮你解决DP O(n)遍历 + Binary Search = O(nlogn)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。