300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
class Solution {
public int lengthOfLIS(int[] nums) {
// 利用二分查找
int length = nums.length;
if (length == 0) return 0;
int[] dp = new int[length];
dp[0] = nums[0];
int res = 1;
int maxIndex = 0;
int left = 0;
int right = 0;
int middle = 0;
for (int i = 1; i < length; ++i) {
if (nums[i] <= dp[0]) dp[0] = nums[i];
else if (nums[i] > dp[maxIndex]) {
++maxIndex;
dp[maxIndex] = nums[i];
} else {
left = 0;
right = maxIndex;
while (left < right) {
if (left + 1 == right) {
dp[right] = nums[i];
break;
}
middle = (left + right) / 2;
if (dp[middle] == nums[i]) {
break;
} else if (dp[middle] < nums[i]) left = middle;
else right = middle;
}
}
res = Math.max(res, maxIndex + 1);
/*
for (int k = 0; k <= maxIndex; ++k) {
if (k == maxIndex) System.out.println(dp[k]);
else System.out.print(dp[k]);
}
*/
}
return res;
}
}