力扣-动态规划-300最长递增子序列

思路 dp数组定义：以i为结尾的字符串的最长子序列为dp[i]递推公式： for(int j = 0; j < i; j++){ if(nums[j] < nums[i]){ dp[i] = max(dp[i], dp[j]+1); } } if(result < dp[i]) result = dp[i]; dp数组初始化：初始为1，即使是遍历顺序：顺序时间复杂度：      代码 class Solution { public: int lengthOfLIS(vector<int>& nums) { vector<int> dp(nums.size(), 1); int result = 1; for(int i = 1; i < nums.size(); i++){ for(int j = 0; j < i; j++){ if(nums[j] < nums[i]){ dp[i] = max(dp[i], dp[j]+1); } } if(result < dp[i]) result = dp[i]; } return result; } };