/C++/Longest increasing subsequence nlogn c++

Longest increasing subsequence nlogn c++

#include <bits/stdc++.h>
using namespace std;
 
int LongestIncreasingSubsequenceLength(std::vector<int>& v)
{
    if (v.size() == 0) // boundary case
        return 0;
 
    std::vector<int> tail(v.size(), 0);
    int length = 1; // always points empty slot in tail
 
    tail[0] = v[0];
 
    for (int i = 1; i < v.size(); i++) {
 
        // Do binary search for the element in
        // the range from begin to begin + length
        auto b = tail.begin(), e = tail.begin() + length;
        auto it = lower_bound(b, e, v[i]);
 
        // If not present change the tail element to v[i]
        if (it == tail.begin() + length)
            tail[length++] = v[i];
        else
            *it = v[i];
    }
 
    return length;
}
 
int main()
{
    std::vector<int> v{ 2, 5, 3, 7, 11, 8, 10, 13, 6 };
    std::cout
        << "Length of Longest Increasing Subsequence is "
        << LongestIncreasingSubsequenceLength(v);
    return 0;
}

-1

Similar codes

0 vote323 views1 answer
Unordered_map header file c++
C++
0 vote297 views1 answer
[3,2,4,-1,-4]
C++
0 vote298 views1 answer
Waiting in a serial as the spool reflect the queue operation. Demonstrate Printer Behavior in context of Queue.Subject to the Scenario implement the Pop and Push Using C++.
C++
0 vote279 views1 answer
Check .h files syntax c++
C++
4 votes321 views2 answers
Getting a random letter in c++
C++
2 votes326 views2 answers
Cannot open include file:
C++
0 vote350 views1 answer
Get bitshift to wrap c++
C++
0 vote280 views1 answer
Generate random ints and floats
C++
0 vote336 views1 answer
C++ power of two
C++
0 vote302 views1 answer
Run c++ files on chrome book
C++