做网站视频赚钱吗,网站开发调研报告,优化师培训机构,回龙观做网站文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a; 程序如下#xff1a;
class Solution {
public:int lengthOfLIS(vectorint nums)… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析 程序如下
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(), 1);int result 1;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i];}return result;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
using namespace std;class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint dp(nums.size(), 1);int result 1;for (int i 1; i nums.size(); i) {for (int j 0; j i; j) {if (nums[i] nums[j]) dp[i] max(dp[i], dp[j] 1);}if (dp[i] result) result dp[i];}return result;}
};int main() {//vectorint nums { 10,9,2,5,3,7,101,18 };vectorint nums { 1, 3, 6, 7, 9, 4, 10, 5, 6 }; Solution s1;int result s1.lengthOfLIS(nums);cout result endl;system(pause);return 0;
}end
