[algorithm] How to determine the longest increasing subsequence using dynamic programming?

The O(NLog(N)) Approach To Find Longest Increasing Sub sequence
Let us maintain an array where the ith element is the smallest possible number with which a i sized sub sequence can end.

On purpose I am avoiding further details as the top voted answer already explains it, but this technique eventually leads to a neat implementation using the set data structure (at least in c++).

Here is the implementation in c++ (assuming strictly increasing longest sub sequence size is required)

#include <bits/stdc++.h> // gcc supported header to include (almost) everything
using namespace std;
typedef long long ll;

int main()
{
  ll n;
  cin >> n;
  ll arr[n];
  set<ll> S;

  for(ll i=0; i<n; i++)
  {
    cin >> arr[i];
    auto it = S.lower_bound(arr[i]);
    if(it != S.end())
      S.erase(it);
    S.insert(arr[i]);
  }

  cout << S.size() << endl; // Size of the set is the required answer

  return 0;
}

Examples related to algorithm

How can I tell if an algorithm is efficient? Find the smallest positive integer that does not occur in a given sequence Efficiently getting all divisors of a given number Peak signal detection in realtime timeseries data What is the optimal algorithm for the game 2048? How can I sort a std::map first by value, then by key? Finding square root without using sqrt function? Fastest way to flatten / un-flatten nested JSON objects Mergesort with Python Find common substring between two strings

Examples related to computer-science

HTML5 Canvas background image What exactly does big ? notation represent? Fixed point vs Floating point number What are the differences between a program and an application? What do we mean by Byte array? How to determine the longest increasing subsequence using dynamic programming? What is "entropy and information gain"? What are the differences between NP, NP-Complete and NP-Hard? What is the difference between statically typed and dynamically typed languages? What is “2's Complement”?

Examples related to dynamic-programming

Find common substring between two strings Difference between Divide and Conquer Algo and Dynamic Programming What is the difference between bottom-up and top-down? How to determine the longest increasing subsequence using dynamic programming? What is dynamic programming?

Examples related to memoization

What is the difference between bottom-up and top-down? How to determine the longest increasing subsequence using dynamic programming? What is memoization and how can I use it in Python? Is there a decorator to simply cache function return values?

Examples related to lis

How to determine the longest increasing subsequence using dynamic programming?