最经典单串：
300. 最长上升子序列 (LIS) https://leetcode-cn.com/problems/longest-increasing-subsequence/submissions/
//GO
//经典DP 线性DP
//dp[i] 那么 nums[i] 必然要大于 nums[j]，才能将 nums[i] 放在nums[j] 后面以形成更长的上升子序列。
func lengthOfLIS(nums []int) int {
if len(nums) <= 1{
return len(nums)
}
var res int
dp := make([]int,len(nums))
dp[0] = 1
//d[0] = nums[0]
for i:=1;i<len(nums);i++{
m := 0
for j:=i-1;j>=0;j--{
if dp[j] > m && nums[j]<nums[i]{
m = dp[j]
}
}
dp[i] = m+1
res = MAX(dp[i],res)
//d[i] = nums[i]
}
return res
} func MAX(i,j int) int{
if i<j{
return j
}else{
return i
}
}
法二：直接求出最长子串 CPP
class Solution {
public:
//最长递增子序列
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i=0;i<nums.size();i++){
if(res.size() ==0 || nums[i] > res.back()){
res.push_back(nums[i]);
continue;
}
int left=0,right=res.size()-1;
while(left<=right){
//找第一个大于等于nums[i]的数，在之前插入
int mid=left+(right-left)/2;
if(nums[i]<= res[mid]) right = mid-1;
else left=mid+1;
}
res[left] = nums[i];
}
return res.size();
}
};