【算法与数据结构】300、LeetCode最长递增子序列

本文介绍: 所有的LeetCode题解索引，可以看这篇文章——。

文章目录

一、题目
二、解法
三、完整代码

所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

在这里插入图片描述

二、解法

思路分析：
程序如下：

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[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
			}
			if (dp[i] > result) result = dp[i];
		}
		return result;
	}
};

复杂度分析：

时间复杂度：
空间复杂度：

三、完整代码

# include <iostream>
# include <vector>
using namespace std;

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[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
			}
			if (dp[i] > result) result = dp[i];
		}
		return result;
	}
};

int main() {
	//vector<int> nums = { 10,9,2,5,3,7,101,18 };
	vector<int> nums = { 1, 3, 6, 7, 9, 4, 10, 5, 6 };	
	Solution s1;
	int result = s1.lengthOfLIS(nums);
	cout << result << endl;
	system("pause");
	return 0;
}