1.题目

2.思路

（1）确定状态
$dp[i]$表示以nums[i]为结尾的最长递增子序列长度（和最大连续子问题一样，以nums[i]结尾是强制的要求）。

（2）状态转移方程
$dp[i]=max(dp[j])+1$，且$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）初始条件+边界情况
$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;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

4.进阶

进阶中时间复杂度达到O(nlog n)，可以参考labuladong该题题解（东哥说一般人想不到，就暂时不理啦hhh）。

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113896223