LeetCode 300最长递增子序列

题目链接：力扣​​​​​​s

思路：动态归划

定义dp数组：设 dp[i] 是以nums[i]结尾的最大递增子序列的长度

状态转移方程：dp[i]=max{dp[j]}+1，当nums[i]>nums[j]，0<=j<i

出口： dp[0]=1

class Solution {public:int lengthOfLIS(vector<int>& nums) {vector<int>dp(nums.size());//注意nums为0的情况if(nums.size()==1)return 1;dp[0]=1;int max_length=0;for(int i=1;i<nums.size();i++){int max_l=0;for(int j=0;j<i;j++){if(nums[j]<nums[i])max_l=max(max_l,dp[j]);}dp[i]=max_l+1;max_length=max(max_length,dp[i]);}return max_length;}};