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
.