title
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Note:
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.
solution
DP
O(n2)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int ans = 0;
int *dp = new int[n + 1];
fill(dp, dp + n + 1, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};
使用一个辅助空间B数组。 Bi存储Dp值为i的最小的数字。（有多个位置，以这些位置为结尾的LIS长度都为i， 则这些数字中最小的一个存在Bi中） 则B数组严格递增。且下标表示LIS长度，也是严格递增，可以在B数组中进行二分查找。
对于每个位置i，我们要找，所有小于Ai, 且Dp值最大的那个。这个操作在B数组中二分查找。
// O(nlogn) Binary Search
public class Solution {
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
public int longestIncreasingSubsequence(int[] nums) {
int[] minLast = new int[nums.length + 1];
minLast[0] = Integer.MIN_VALUE;
for (int i = 1; i <= nums.length; i++) {
minLast[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < nums.length; i++) {
// find the first number in minLast >= nums[i]
int index = binarySearch(minLast, nums[i]);
minLast[index] = nums[i];
}
for (int i = nums.length; i >= 1; i--) {
if (minLast[i] != Integer.MAX_VALUE) {
return i;
}
}
return 0;
}
// find the first number > num
private int binarySearch(int[] minLast, int num) {
int start = 0, end = minLast.length - 1;
while (start + 1 < end) {
int mid = (end - start) / 2 + start;
if (minLast[mid] < num) {
start = mid;
} else {
end = mid;
}
}
return end;
}
}