300.最长递增子序列

方法1:动态规划

思路：

dp[i]表示截止到 i 最长的子序列长度

首先更新所有dp[i]=1，表示至少单个字符可以当作最短的子序列

对于每一个dp[i]，用 j 遍历原数组nums中 [ 0 , i ] 这个区间

如果nums[j] >= nums[i] ，非递增 不考虑

如果nums[j] < nums[i]，此时是递增，那么到 i 最长的子序列= 到 j 最长的子序列 + nums[i] ，dp[i] = dp[j] + 1

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n=nums.size();//初始化为1vector<int>dp(n,1);for(int i=0;i<n;i++){for(int j=0;j<i;j++){if(nums[j] < nums[i]){//一个i对应好几个j，最终的dp[i]取最大的一个，随时比较更新dp[i] = max(dp[i],dp[j] + 1);}}}return *max_element(dp.begin(),dp.end());}
};

方法2:动态规划+二分查找 O(n log(n))复杂度

暂时懒得看