力扣300.最长递增子序列（动态规划）

注：本文只是为了记录作者在刷题过程中的一下思路和心得。

思路：每次考虑以第 i 个元素结尾时能够构成的最长子序列。

例如：nums = [0,1,3,2] , 我们从下标为0的元素开始考虑，如果以下标为0的元素结尾，那么这个子序列的长度就为1；然后依次我们考虑后面的元素。当我们考虑到第 i 个元素时，需要依次去检查前面0~i-1的元素中，值比nums[i]小但长度最大的那个，然后取最大值。(具体看代码注释！！)

代码如下：

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n=nums.size();  //获取nums数组长度
        vector<int> dp(n,1);  //建立dp数组
        for(int i=1;i<n;i++){   //从头到尾开始考虑
            for(int j=0;j<i;j++){    //当考虑到第i个元素时，去检查前面i-1个元素
                if(nums[j]<nums[i]){    //以当前结尾的子序列的最大值
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        int ans=dp[0];           //记录最长子序列的值
        for(int i=1;i<n;i++){    //查找dp数组中的最大值
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

上面的dp数组的含义是：以第 i 个元素结尾的最长子序列长度，他依靠前面的元素，取前面的nums 元素比nums[i] 小但长度最长的子序列加一。