LeetCode/最大递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
1. 动态规划
dp[i]表示以i结尾的最长长度
状态转移方程dp[i] = max(dp[j])+1 if num[j]
边界条件 dp[0] = 1
时间复杂度为O(n2)，即遍历一遍，同时对每个元素往前搜索一遍
动态规划
class Solution {
public:
int lengthOfLIS(vector& nums) {
//动态规划
int n = nums.size();
if(n==0) return 0;
vector dp(n); //dp[i]表示以i结尾的最长长度
int res = 0;
for(int i=0;i 2. 动态规划优化
注意到方法一反向搜索时，要找的是序列末位元素小于当前元素的最大序列长度
我们关心的只是某一序列长度的最小末尾元素，所以dp[i]可以表示为序列长度为i的最小末尾元素值
这样不仅能减少查找的数据量，还能使用二分法进行查找
class Solution {
public:
int lengthOfLIS(vector& nums) {
//动态规划
int n = nums.size();
if(n==0) return 0;
vector dp(n); //dp[i]记录i长度序列的最后元素值
int res = 0;
for(int k=0;k