Hey, so today we are going to solve Leetcode - Longest Increasing Subsequence
Problem Link- https://leetcode.com/problems/longest-increasing-subsequence
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int i =0; i<nums.size(); i++){
auto it = lower_bound(res.begin(), res.end(), nums[i]);
if(it == nums.end()){
res.emplace_back(nums[i]);
}
else {
*it = nums[i];
}
}
return res.size();
}
}
The class
Solution
contains a member functionlengthOfLIS
that takes a vectornums
as input and returns an integer representing the length of the Longest Increasing Subsequence (LIS) within the vector.Inside the function, a vector
res
is declared, which will store the LIS elements.A loop is used to iterate through each element of the
nums
vector.For each element,
std::lower_bound
is used to find the position where the element can be inserted in theres
vector while maintaining the increasing order.If the iterator
it
points to the end of theres
vector, it means that the current element is greater than all the elements inres
. In this case, the current element is appended to the end ofres
.If the iterator
it
points to a valid position within theres
vector, it means that the current element can replace an existing element and still maintain the increasing order. Therefore, the element at positionit
is updated with the current element.After iterating through all the elements of
nums
, the length of the LIS is equal to the size of theres
vector.
Now, let's visualize the code using an example:
nums: [10, 9, 2, 5, 3, 7, 101, 18]
Initially, the res
vector is empty.
Step 1:
Current element: 10
res
: [10]
Step 2:
Current element: 9
res
: [9]
Step 3:
Current element: 2
res
: [2]
Step 4:
Current element: 5
res
: [2, 5]
Step 5:
Current element: 3
res
: [2, 3]
Step 6:
Current element: 7
res
: [2, 3, 7]
Step 7:
Current element: 101
res
: [2, 3, 7, 101]
Step 8:
Current element: 18
res
: [2, 3, 7, 18]
Finally, the function returns the size of the res
vector, which is 4, representing the length of the Longest Increasing Subsequence in the given vector nums
.
Subscribe to our newsletter
Read articles from An Explorer directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Article Series
Data Structures & Algorithms
DSA - Evaluate Division - C++,Graph, DFS
Hey, so today we are going to solve Leetcode - Evaluate Division Problem Link- https://leetcode.com/…
DSA - Triangle - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Triangle Problem Link- https://leetcode.com/problems/…
DSA - Minimum Path Sum - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Minimum Path Sum Problem Link- https://leetcode.com/p…
DSA - Maximize Score after N Operations - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Maximize Score after N Operations Problem Link- https…
DSA - Non decreasing Subsequences - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Non decreasing Subsequences Problem Link- https://lee…
DSA - Maximum Length of Pair Chain - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Maximum Length of Pair Chain Problem Link- https://le…
DSA - Longest Increasing Subsequence - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Longest Increasing Subsequence Problem Link- https://…
DSA - Decode Ways - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Decode Ways Problem Link- https://leetcode.com/proble…
DSA - letter combinations of a phone number - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - letter combinations of a phone number Problem Link- h…
DSA - generate-parentheses - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Generate Parentheses Problem Link- https://leetcode.c…
DSA - longest Substring - C++,Dynamic Programming
Hey, so today we are going to solve Leetcode - Longest Palindromic Substring Problem Link- https://l…