Particionar una array en segmentos crecientes máximos

Nos dan una array de N enteros, necesitamos dividir la array en segmentos de modo que cada elemento de un segmento sea mayor que cada elemento del segmento anterior. En otras palabras, si ordenamos estos segmentos individuales, se ordena toda la array. Necesitamos encontrar una partición válida con el número máximo de subarreglos. 
Ejemplos: 
 

arr[] = {3 1 2 4 100 7 9} 
Salida: 3 
Debe dividir la array en las siguientes subarreglas: (3, 1, 2), (4) y (100, 7, 9).
Entrada: arr[] = {2 1 2 3 3 4 3} 
Salida: 5

Enfoque Un enfoque codicioso funciona muy bien ya que conduce al siguiente algoritmo. Encuentre el prefijo más corto de modo que todos los elementos del prefijo sean menores o iguales que los elementos del resto de la array.
Considere este prefijo como el primer subarreglo de la partición. Llame recursivamente al mismo algoritmo en el resto de la array. En cuanto a la implementación, podemos preprocesar una array de valores máximos para cada prefijo y otra array de valores mínimos para cada sufijo. De esta forma, podemos realizar fácilmente una verificación para ver si un prefijo determinado es un candidato viable para un subarreglo de partición.
A continuación se muestra la implementación del enfoque anterior:
 

// C++ program to divide into maximum number of segments
 
#include <iostream>
using namespace std;
 
    // Returns the maximum number of sorted subarrays
    // in a valid partition
    int sorted_partitions(int arr[],int n)
    {
         
        int right_min[n + 1];
        right_min[n] = INT8_MAX;
        for (int i = n - 1; i >= 0; i--) {
            right_min[i] = min(right_min[i + 1], arr[i]);
        }
 
        // Finding the shortest prefix such that all the elements
        // in the prefix are less than or equal to the elements
        // in the rest of the array.
        int partitions = 0;
        for (int current_max = arr[0], i = 0; i < n; i++) {
            current_max = max(current_max, arr[i]);
           
            // if current max is less than the right prefix min,
            // we increase number of partitions.
            if (current_max <= right_min[i + 1])
                partitions++;
        }
 
        return partitions;
    }
 
    // Driver code
    int main()
    {
        int arr[] = { 3, 1, 2, 4, 100, 7, 9 };
        // Find minimum value from right for every index
        int n = sizeof(arr)/sizeof(arr[0]);
         
        int ans = sorted_partitions(arr,n);
        cout << ans << endl;
        return 0;
         
    // This code is contributed by ANKITRAI1
    }

// Java program to divide into maximum number of segments
import java.util.Arrays;
 
class GFG {
 
    // Returns the maximum number of sorted subarrays
    // in a valid partition
    static int sorted_partitions(int arr[])
    {
        // Find minimum value from right for every index
        int n = arr.length;
        int[] right_min = new int[n + 1];
        right_min[n] = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            right_min[i] = Math.min(right_min[i + 1], arr[i]);
        }
 
        // Finding the shortest prefix such that all the elements
        // in the prefix are less than or equal to the elements
        // in the rest of the array.
        int partitions = 0;
        for (int current_max = arr[0], i = 0; i < n; i++) {
            current_max = Math.max(current_max, arr[i]);
           
            // if current max is less than the right prefix min,
            // we increase number of partitions.
            if (current_max <= right_min[i + 1])
                partitions++;
        }
 
        return partitions;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = new int[] { 3, 1, 2, 4, 100, 7, 9 };
        int ans = sorted_partitions(arr);
        System.out.println(ans);
    }
}

# Python 3 program to divide into
# maximum number of segments
import sys
 
# Returns the maximum number of sorted
# subarrays in a valid partition
def sorted_partitions( arr, n):
     
    right_min = [0] * (n + 1)
    right_min[n] = sys.maxsize
    for i in range(n - 1, -1, -1):
        right_min[i] = min(right_min[i + 1], arr[i])
     
    # Finding the shortest prefix such that
    # all the elements in the prefix are less
    # than or equal to the elements in the
    # rest of the array.
    partitions = 0
    current_max = arr[0]
    for i in range(n):
        current_max = max(current_max, arr[i])
         
        # if current max is less than the right
        # prefix min, we increase number of partitions.
        if (current_max <= right_min[i + 1]):
            partitions += 1
 
    return partitions
 
# Driver code
arr = [ 3, 1, 2, 4, 100, 7, 9 ]
 
# Find minimum value from right
# for every index
n = len(arr)
ans = sorted_partitions(arr, n)
print(ans)
     
# This code is contributed by ita_c

// C# program to divide into maximum number of segments
using System;
 
class GFG {
 
    // Returns the maximum number of sorted subarrays
    // in a valid partition
    static int sorted_partitions(int []arr)
    {
        // Find minimum value from right for every index
        int n = arr.Length;
        int[] right_min = new int[n + 1];
        right_min[n] =  int.MaxValue;
        for (int i = n - 1; i >= 0; i--) {
            right_min[i] = Math.Min(right_min[i + 1], arr[i]);
        }
 
        // Finding the shortest prefix such that all the elements
        // in the prefix are less than or equal to the elements
        // in the rest of the array.
        int partitions = 0;
        for (int current_max = arr[0], i = 0; i < n; i++) {
            current_max = Math.Max(current_max, arr[i]);
         
            // if current max is less than the right prefix min,
            // we increase number of partitions.
            if (current_max <= right_min[i + 1])
                partitions++;
        }
 
        return partitions;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 3, 1, 2, 4, 100, 7, 9 };
        int ans = sorted_partitions(arr);
        Console.WriteLine(ans);
    }
}
// This code is contributed by anuj_67..

<?php
// PHP program to divide into maximum
// number of segments
 
// Returns the maximum number of
// sorted subarrays in a valid partition
function sorted_partitions($arr, $n)
{
     
    $right_min[$n + 1] = array();
    $right_min[$n] = PHP_INT_MAX;
    for ( $i = $n - 1; $i >= 0; $i--)
    {
        $right_min[$i] = min($right_min[$i + 1],
                                        $arr[$i]);
    }
 
    // Finding the shortest prefix such
    // that all the elements in the prefix
    // are less than or equal to the elements
    // in the rest of the array.
    $partitions = 0;
    for ($current_max = $arr[0],
                        $i = 0; $i < $n; $i++)
    {
        $current_max = max($current_max, $arr[$i]);
         
        // if current max is less than the
        // right prefix min, we increase
        // number of partitions.
        if ($current_max <= $right_min[$i + 1])
            $partitions++;
    }
 
    return $partitions;
}
 
// Driver code
$arr = array( 3, 1, 2, 4, 100, 7, 9 );
 
// Find minimum value from
// right for every index
$n = sizeof($arr);
 
$ans = sorted_partitions($arr, $n);
echo $ans, "\n";
 
// This code is contributed by ajit
?>

<script>
    // Javascript program to divide into maximum number of segments
     
    // Returns the maximum number of sorted subarrays
    // in a valid partition
    function sorted_partitions(arr)
    {
        // Find minimum value from right for every index
        let n = arr.length;
        let right_min = new Array(n + 1);
        right_min.fill(0);
        right_min[n] =  Number.MAX_VALUE;
        for (let i = n - 1; i >= 0; i--) {
            right_min[i] = Math.min(right_min[i + 1], arr[i]);
        }
   
        // Finding the shortest prefix such that all the elements
        // in the prefix are less than or equal to the elements
        // in the rest of the array.
        let partitions = 0;
        for (let current_max = arr[0], i = 0; i < n; i++) {
            current_max = Math.max(current_max, arr[i]);
           
            // if current max is less than the right prefix min,
            // we increase number of partitions.
            if (current_max <= right_min[i + 1])
                partitions++;
        }
   
        return partitions;
    }
     
    let arr = [ 3, 1, 2, 4, 100, 7, 9 ];
    let ans = sorted_partitions(arr);
    document.write(ans);
         
</script>

3

Análisis de rendimiento:

Complejidad de tiempo: O(n), ya que se utiliza un solo recorrido en la función sorted_partitions().

Complejidad espacial: O(n), declaramos una array de tamaño n+1 en la función sorted_partitions().