【Lintcode】076.Longest Increasing Subsequence
2024-08-23 19:52:31
题目：
Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.
Clarification
What's the definition of longest increasing subsequence?
The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4
题解：
For dp[i], dp[i] is max(dp[j]+1, dp[i]), for all j < i and nums[j] < nums[i].
Solution 1 ()
class Solution {
public:
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.empty()) {
return ;
}
vector<int> dp(nums.size(), );
int res = ;
for (int i = ; i < nums.size(); ++i) {
for (int j = ; j < i; ++j) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + );
}
}
res = max(dp[i], res);
}
return res;
}
};
Solution 2 ()
class Solution {
public:
/**
* @param nums: The integer array
* @return: The length of LIS (longest increasing subsequence)
*/
int longestIncreasingSubsequence(vector<int> nums) {
vector<int> res;
for(int i=; i<nums.size(); i++) {
auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
};
Solution 3 ()
class Solution {
public:
int longestIncreasingSubsequence(vector<int> nums) {
if (nums.empty()) {
return ;
}
vector<int> tmp;
tmp.push_back(nums[]);
for (auto num : nums) {
if (num < tmp[]) {
tmp[] = num;
} else if (num > tmp.back()) {
tmp.push_back(num);
} else {
int begin = , end = tmp.size();
while (begin < end) {
int mid = begin + (end - begin) / ;
if (tmp[mid] < num) {
begin = mid + ;
} else {
end = mid;
}
}
tmp[end] = num;
}
}
return tmp.size();
}
};
最新文章
- 你所不知道的SQL Server数据库启动过程（用户数据库加载过程的疑难杂症）
- springMvc源码学习之：spirngMVC获取请求参数的方法2
- C#时间处理--DateTime和TimeSpan
- Java与MySql数据类型对照表
- 新浪微博、腾讯微博、QQ空间、人人网、豆瓣 一键分享API
- C# 面向对象编程的继承性-多继承
- js常用 禁止F5 和右键
- block 做参数
- DataTables给表格绑定事件
- 【HELLO WAKA】WAKA iOS客户端 之二 架构设计与实现篇
- js登录，回车登录
- Leetcode_202_Happy Number
- 与其想当然的 overdesign，不如自己动手做个试验
- Win7远程桌面：发生身份验证错误
- 【AtCoder】ARC076
- 尝试IRC & freenode
- [pytorch修改]dataloader.py 实现darknet中的subdivision功能
- (转)Java中equals和==、hashcode的区别
- char/unsigned char/int/short 存储范围
- Axure 图片轮播（广告通栏图片自动播放效果）