1.题目
2.思路
（1）确定状态
d p [ i ] dp[i]dp[i]表示以nums[i]为结尾的最长递增子序列长度（和最大连续子问题一样，以nums[i]结尾是强制的要求）。
（2）状态转移方程
d p [ i ] = m a x ( d p [ j ] ) + 1 dp[i]=max(dp[j])+1dp[i]=max(dp[j])+1，且0 < = j < i ， n u m s [ j ] < n u m [ i ] 0<=j<i，nums[j]<num[i]0<=j<i，nums[j]<num[i]。
——举个栗子：序列{1，5，1，3}=nums[0、1、2、3]（简写了），以nums[0]、nums[1]、nums[2]为结尾的最长递增子序列分别为{1}、{1,5}、{-1}，即长度分别为1、2、1。而现在要求以nums[3]为结尾的最长递增序列及其长度，即要将nums[3]分别加到前面说的三个最长递增序列中（康康是否合法），若合法即要求最大的那个，并把nums[3]加入后，使得最长递增序列长度加1。
（3）初始条件+边界情况
d p [ i ] dp[i]dp[i]=1，即假设初始每个元素自成一个自序列。
（4）计算顺序
i从0到n-1，j从0到i。
3.代码
class Solution { public: int lengthOfLIS(vector<int>& nums) { int n=nums.size(); if(n==0) return 0; vector<int>dp(n+1,1); //dp[i]=1;//边界初始条件（即先假设每个元素自成一个子序列） for(int i=0;i<n;i++){ //dp[i]=1;//边界初始条件（即先假设每个元素自成一个子序列） for(int j=0;j<i;j++){ if(nums[i]>nums[j] ){ dp[i]=max(dp[i],dp[j]+1);//状态转移方程，用以更新dp[i] } } } int ans=*max_element(dp.begin(),dp.end()); return ans; } };
