Tamaño de subsecuencia monótonamente creciente más largo (N log N): Implementación simple

Dada una array de números aleatorios, encuentre la subsecuencia creciente monótonamente más larga (LIS) en la array. Si desea comprender el enfoque O (NlogN), se explica muy claramente aquí .

En esta publicación, se analiza una implementación simple y que ahorra tiempo del enfoque O (NlogN) utilizando stl. A continuación se muestra el código para LIS O (NlogN):

Implementación:

// C++ implementation
// to find LIS
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
 
// Return length of LIS in arr[] of size N
int lis(int arr[], int N)
{
    int i;
    set<int> s;
    set<int>::iterator k;
    for (i=0; i<N; i++)
    {
        // Check if the element was actually inserted
        // An element in set is not inserted if it is
        // already present. Please see
        // https://www.geeksforgeeks.org/set-insert-function-in-c-stl/
        if (s.insert(arr[i]).second)
        {
            // Find the position of inserted element in iterator k
            k = s.find(arr[i]);
 
            k++;  // Find the next greater element in set
 
            // If the new element is not inserted at the end, then
            // remove the greater element next to it (This is tricky)
            if (k!=s.end()) s.erase(k);
        }
    }
 
    // Note that set s may not contain actual LIS, but its size gives
    // us the length of LIS
    return s.size();
}
 
int main()
{
    int arr[] = {8, 9, 12, 10, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << lis(arr, n)<< endl;
}

// Java implementation
// to find LIS
import java.util.*;
class GFG{
 
// Return length of LIS
// in arr[] of size N
static int lis(int arr[],
               int N)
{
  int i;
  HashSet<Integer> s = new HashSet<>();
  for (i = 0; i < N; i++)
  {
    // Check if the element
    // was actually inserted
    // An element in set is
    // not inserted if it is
    // already present. Please see
    // https://www.geeksforgeeks.
    // org/set-insert-function-in-c-stl/
    int k = 0;
    int size = s.size();
    if (s.add(arr[i]))
    {
      // Find the position of
      // inserted element in iterator k
      if(s.contains(arr[i]))
        k++; 
       
      // Find the next
      // greater element in set
      // If the new element is not
      // inserted at the end, then
      // remove the greater element
      // next to it.
      if (size == s.size())
        s.remove(k + 1);
    }
  }
 
  // Note that set s may not contain
  // actual LIS, but its size gives
  // us the length of LIS
  return s.size();
}
 
public static void main(String[] args)
{
  int arr[] = {8, 9, 12, 10, 11};
  int n = arr.length;
  System.out.print(lis(arr, n) + "\n");
}
}
 
// This code is contributed by gauravrajput1

# Python implementation
# to find LIS
 
# Return length of LIS
# in arr of size N
def lis(arr, N):
    s = set();
    for i in range(N):
       
        # Check if the element
        # was actually inserted
        # An element in set is
        # not inserted if it is
        # already present. Please see
        # https:#www.geeksforgeeks.
        # org/set-insert-function-in-c-stl/
        k = 0;
        size = len(s);
        if (s.add(arr[i])):
           
            # Find the position of
            # inserted element in iterator k
            if arr[i] in s:
                k += 1;
 
            # Find the next
            # greater element in set
            # If the new element is not
            # inserted at the end, then
            # remove the greater element
            # next to it.
            if (size == len(s)):
                s.remove(k + 1);
         
    # Note that set s may not contain
    # actual LIS, but its size gives
    # us the length of LIS
    return len(s);
 
# Driver code
if __name__ == '__main__':
    arr = [ 8, 9, 12, 10, 11 ];
    n = len(arr);
    print(lis(arr, n) ,"");
 
# This code is contributed by Rajput-Ji

// C# implementation
// to find LIS
using System;
using System.Collections.Generic;
 
class GFG{
     
// Return length of LIS
// in arr[] of size N
static int lis(int[] arr, int N)
{
    int i;
    HashSet<int> s = new HashSet<int>();
    for(i = 0; i < N; i++)
    {
         
        // Check if the element was actually inserted
        // An element in set is not inserted if it is
        // already present. Please see
        // https://www.geeksforgeeks.org/set-insert-function-in-c-stl/
        int k = 0;
        int size = s.Count;
         
        if (s.Add(arr[i]))
        {
             
            // Find the position of inserted
            // element in iterator k
            if (s.Contains(arr[i]))
                k++;
             
            // Find the next greater element in set
            // If the new element is not inserted at
            // the end, then remove the greater element
            // next to it.
            if (size == s.Count)
                s.Remove(k + 1);
        }
    }
     
    // Note that set s may not contain
    // actual LIS, but its size gives
    // us the length of LIS
    return s.Count;
}
 
// Driver code
static public void Main()
{
    int[]    arr = { 8, 9, 12, 10, 11 };
    int n = arr.Length;
     
    Console.Write(lis(arr, n) + "\n");
}
}
 
// This code is contributed by avanitrachhadiya2155

<script>
 
// Javascript implementation
// to find LIS
 
// Return length of LIS
// in arr[] of size N
function lis(arr,N)
{
    let i;
  let s = new Set();
  for (i = 0; i < N; i++)
  {
    // Check if the element
    // was actually inserted
    // An element in set is
    // not inserted if it is
    // already present. Please see
    // https://www.geeksforgeeks.
    // org/set-insert-function-in-c-stl/
    let k = 0;
    let size = s.size;
    if (s.add(arr[i]))
    {
      // Find the position of
      // inserted element in iterator k
      if(s.has(arr[i]))
        k++;
        
      // Find the next
      // greater element in set
      // If the new element is not
      // inserted at the end, then
      // remove the greater element
      // next to it.
      if (size == s.size)
        s.delete(k + 1);
    }
  }
  
  // Note that set s may not contain
  // actual LIS, but its size gives
  // us the length of LIS
  return s.size;
}
 
let arr=[8, 9, 12, 10, 11];
let n = arr.length;
document.write(lis(arr, n) + "<br>");
 
// This code is contributed by unknown2108
 
</script>

4