Repository: TheAlgorithms/C-Plus-Plus
File: search/Longest_Increasing_Subsequence_using_binary_search.cpp (C++)

Code before:
}

/**
 * @brief Test cases for Longest Increasing Subsequence function
 * @returns void
 */
static void tests() {
    std::vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
    assert(longest_increasing_subsequence_using_binary_search(arr) == 4);

    std::vector<int> arr2 = {0, 1, 0, 3, 2, 3};
    assert(longest_increasing_subsequence_using_binary_search(arr2) == 4);

    std::vector<int> arr3 = {7, 7, 7, 7, 7, 7, 7};
    assert(longest_increasing_subsequence_using_binary_search(arr3) == 1);

    std::cout << "All tests have successfully passed!\n";
}

/**
 * @brief Main function to run tests
 * @returns 0 on exit
 */
int main() {
    tests();
    return 0;
}


Review comment (security):
needs a header comment explaining the algorithm, if relevant math formulas in latex format, authors name

this is the format;
```cpp
/**
 * @file
 * @brief Add one-line description here. Should contain a Wikipedia
 * link or another source explaining the algorithm/implementation.
 * @details
 * This is a multi-line
 * description containing links, references,
 * math equations, etc.
 * @author [Name](https://github.com/handle)
 * @see related_file.cpp, another_file.cpp
 */
 ```

Code after:
 * 1. We only consider the element in the subsequence if the element is grater then
 * the last element present in the subsequence
 * 2. When we consider the element we will increase the length of subsequence by 1
 * Time Complexity: O(N*N)
 * Space Complexity: O(N*N) + O(N)

 * This approach is better then the previous Brute Force approach so, we can
 * consider this approach.

 * But when the Constraints for the problem is very larger then this approach fails

 * Approach 3 :- Using Binary Search
 * Other approaches use additional space to create a new subsequence Array.
 * Instead, this solution uses the existing nums Array to build the subsequence
 * array. We can do this because the length of the subsequence array will never be
 * longer than the current index.

 * Time complexity: O(n∗log(n))
 * Space complexity: O(1)

 * This approach consider Most optimal Approach for solving this problem

 * @author [Naman Jain](https://github.com/namanmodi65)
 */

#include <cassert>   /// for std::assert
#include <iostream>  /// for IO operations
#include <vector>    /// for std::vector
#include <algorithm> /// for std::lower_bound
#include <cstdint>   /// for std::uint32_t

/**
 * @brief Function to find the length of the Longest Increasing Subsequence (LIS)
 * using Binary Search
 * @tparam T The type of the elements in the input vector
 * @param nums The input vector of elements of type T
 * @return The length of the longest increasing subsequence
 */
template <typename T>
std::uint32_t longest_increasing_subsequence_using_binary_search(std::vector<T>& nums) {
    if (nums.empty()) return 0;

    std::vector<T> ans;
    ans.push_back(nums[0]);
    for (std::size_t i = 1; i < nums.size(); i++) {
        if (nums[i] > ans.back()) {
            ans.push_back(nums[i]);
        } else {
            auto idx = std::lower_bound(ans.begin(), ans.end(), nums[i]) - ans.begin();
            ans[idx] = nums[i];
        }