Número mínimo de subsecuencias crecientes

Dada una array de números enteros de tamaño N, debe dividirla en el número mínimo de «subsecuencias estrictamente crecientes». 
Por ejemplo: sea la secuencia {1, 3, 2, 4}, entonces la respuesta sería 2. En este caso, la primera secuencia creciente sería {1, 3, 4} y la segunda sería {2}.
Ejemplos:

 
Entrada: arr[] = {1 3 2 4} 
Salida: 2 
Hay dos subsecuencias crecientes {1, 3, 4} y {2}
Entrada: arr[] = {4 3 2 1} 
Salida: 4
Entrada: arr[ ] = {1 2 3 4} 
Salida : 1
Entrada : arr[] = {1 6 2 4 3} 
Salida : 3

Si nos enfocamos en el ejemplo, podemos ver que el número mínimo de subsecuencias crecientes es igual a la longitud de la subsecuencia decreciente más larga donde cada elemento de la subsecuencia decreciente más larga representa una subsecuencia creciente, por lo que se puede encontrar en N*Log(N) tiempo complejidad de la misma manera que la subsecuencia creciente más larga multiplicando todos los elementos con -1. 
Iteramos sobre todos los elementos y los almacenamos en una array ordenada ( multiset) S el último elemento en cada una de las subsecuencias crecientes encontradas hasta ahora y para cada elemento X, seleccionamos el elemento más grande más pequeño que X -usando búsqueda binaria- en S y lo reemplazamos con X, lo que significa que agregamos el elemento actual a una subsecuencia creciente que termina en X, de lo contrario, si no hay ningún elemento menor que X en S, lo insertamos en S, lo que forma una nueva subsecuencia creciente y así hasta el último elemento y nuestra respuesta en el último será del tamaño de S.

// C++ program to count the Minimum number of
// increasing subsequences
#include <bits/stdc++.h>
using namespace std;
 
int MinimumNumIncreasingSubsequences(int arr[], int n)
{
    multiset<int> last;
 
    // last element in each  increasing subsequence
    // found so far
    for (int i = 0; i < n; i++) {
 
        // here our current element is arr[i]
        multiset<int>::iterator it = last.lower_bound(arr[i]);
 
        // iterator to the first element larger
        // than or equal to arr[i]
        if (it == last.begin())
 
            // if all the elements in last larger
            // than or to arr[i] then insert it into last
            last.insert(arr[i]);
 
        else {
            it--;
 
            // the largest element smaller than arr[i] is the number
            // before *it which is it--
            last.erase(it); // erase the largest element smaller than arr[i]
            last.insert(arr[i]); // and replace it with arr[i]
        }
    }
    return last.size(); // our answer is the size of last
}
 
// Driver program
int main()
{
    int arr[] = { 8, 4, 1, 2, 9 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Minimum number of increasing subsequences are : "
         << MinimumNumIncreasingSubsequences(arr, n);
    return 0;
}

Minimum number of increasing subsequences are : 3

Complejidad temporal: O(N log(N)) 
Espacio auxiliar: O(N) 
Enfoque 2 : La idea es encontrar la subsecuencia decreciente más larga

• Inicialice una array dp de longitud n.
• Invertir todos los elementos de la array.
• para cada elemento de la array.
• encuentre el índice si el elemento actual en la array dp.
• encontrar el índice máximo que es válido.
• dp[i] indica que el elemento mínimo termina en la subsecuencia de longitud i.

A continuación se muestra la implementación del enfoque anterior :

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// To search for correct position of num in array dp
int search(vector<int>dp, int num){
 
    // Initialise low,high and ans
    int low = 0,high = dp.size() - 1;
    int ans = -1;
    while (low <= high){
 
        // Get mid
        int mid = low + ((high - low) / 2);
 
        // If mid element is >=num search for left half
        if (dp[mid] >= num){
            ans = mid;
            high = mid - 1;
        }
         
        else
            low = mid + 1;
    }
    return ans;
}
 
int longestDecrasingSubsequence(vector<int>A,int N){
 
    // Initialise Dp array
    vector<int>dp(N+1,INT_MAX);
 
    // All the elements are in range
    // of integer minvalue
    // to maxvalue
    // dp[i] indicate the min element
    // of subsequence of
    // length i is dp[i]
    dp[0] = INT_MIN;
     
    // For each number search for the correct position
    // of number and insert the number in array
    for(int i = 0; i < N; i++){
 
        // search for the position
        int index = search(dp, A[i]);
 
        // update the dp array
        if (index != -1)
            dp[index] = min(dp[index], A[i]);
    }
     
    int Len = 0;
    for(int i = 1; i < N; i++){
        if (dp[i] != INT_MAX)
            Len = max(i, Len);
 
    }
    return Len;
}
 
// Driver code
int main()
{
    int n = 4;
    vector<int> a = { 1, 2, 3, 4 };
    for(int i=0;i<n;i++)
        a[i] = -a[i];
 
    cout << longestDecrasingSubsequence(a, n) << endl;
    return 0;
}
 
// This code is contributed by shinjanpatra

// Java program for the above approach
import java.util.*;
public class Main {
      
    static int longestDecrasingSubsequence(int A[], int N)
    {
        // Initialise Dp array
        int dp[] = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
       
        // All the elements are in range
        // of Integer minvalue
        // to maxvalue
        // dp[i] indicate the min element
        // of subsequence of
        // length i is dp[i]
        dp[0] = Integer.MIN_VALUE;
       
        // For each number search for the correct position
        // of number and insert the number in array
        for (int i = 0; i < N; i++) {
           
            // search for the position
            int index = search(dp, A[i]);
           
            // update the dp array
            if (index != -1)
                dp[index] = Math.min(dp[index], A[i]);
        }
        int len = 0;
        for (int i = 1; i <= N; i++) {
            if (dp[i] != Integer.MAX_VALUE)
                len = Math.max(i, len);
        }
        return len;
    }
   
    // to search for correct position of num in array dp
    static int search(int dp[], int num)
    {
        
        // initialise low,high and ans
        int low = 0, high = dp.length - 1;
        int ans = -1;
        while (low <= high) {
 
            // get mid
            int mid = low + (high - low) / 2;
           
            // if mid element is >=num search for left half
            if (dp[mid] >= num) {
                ans = mid;
                high = mid - 1;
            }
            else
                low = mid + 1;
        }
        return ans;
    }
    // Driver Code
    public static void main(String args[])
    {
 
        int n = 4;
        int a[] = { 1, 2, 3, 4 };
        for (int i = 0; i < n; i++)
            a[i] = -a[i];
        System.out.print(longestDecrasingSubsequence(a, n));
    }
}

# Python program for the above approach
import sys
 
def longestDecrasingSubsequence(A,N):
 
    # Initialise Dp array
    dp = [sys.maxsize for i in range(N+1)]
 
    # All the elements are in range
    # of integer minvalue
    # to maxvalue
    # dp[i] indicate the min element
    # of subsequence of
    # length i is dp[i]
    dp[0] = -sys.maxsize -1
     
    # For each number search for the correct position
    # of number and insert the number in array
    for i in range(N):
 
        # search for the position
        index = search(dp, A[i])
 
        # update the dp array
        if (index != -1):
            dp[index] = min(dp[index], A[i])
     
    Len = 0
    for i in range(1,N):
        if (dp[i] != sys.maxsize):
            Len = max(i, Len)
 
    return Len
 
# to search for correct position of num in array dp
def search(dp, num):
 
    # initialise low,high and ans
    low,high = 0, len(dp) - 1
    ans = -1
    while (low <= high):
 
        # get mid
        mid = low + (high - low) // 2
 
        # if mid element is >=num search for left half
        if (dp[mid] >= num):
            ans = mid
            high = mid - 1
         
        else:
            low = mid + 1
 
    return ans
 
# Driver Code
n = 4
a = [ 1, 2, 3, 4 ]
for i in range(n):
    a[i] = -a[i]
 
print(longestDecrasingSubsequence(a, n))
 
# This code is contributed by shinjanpatra

1