1、题目
image.png
2、分析
（1）动态规划：只需要找到转移方程即可。
（2）二分查找法：
本题分析：
https://labuladong.github.io/zgnb/3/15/16/
二分查找法原理：
https://www.cnblogs.com/labuladong/p/12320448.html
3、代码
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
// base case：dp 数组全都初始化为 1
Arrays.fill(dp, 1);
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
//找到前面比它小的元素
if (nums[i] > nums[j])
//该元素的最长子序列，等于前面小元素的dp最大值+ 1
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
int res = 0;
for (int i = 0; i < dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
二分查找法代码：
class Solution {
public int lengthOfLIS(int[] nums) {
int piles = 0;
int[] arr = new int[nums.length];
for(int i = 0; i < nums.length; i++){
int val = nums[i];
int left = 0;
int right = piles;
while(left < right){
int mid = (left + right) / 2;
if(arr[mid] == val){
right = mid;
}else if(arr[mid] < val){
left = mid + 1;
}else{
right = mid;
}
}
if(left == piles) piles++;
arr[left] = val;
}
return piles;
}
}
