Maximice las particiones que, si se ordenan individualmente, hacen que se ordene toda la array

Dada una array arr[] . La tarea es dividir arr[] en el número máximo de particiones, de modo que esas particiones, si se ordenan individualmente, hacen que se ordene toda la array.

Ejemplos:

Entrada: arr[] = { 28, 9, 18, 32, 60, 50, 75, 70 }
Salida: 4
Explicación: Las siguientes son las particiones en las que se divide la array. 
Si dividimos arr[] en cuatro particiones {28, 9, 18}, {32}, {60, 50} y {75, 70}, ordénelas y concatene. 
Clasificarlos todos individualmente hace que se ordene toda la array. 
Por lo tanto, 4 es la respuesta.

Entrada: arr[] = { 2, 1, 0, 3, 4, 5 }
Salida: 4

Enfoque: Este problema está basado en la implementación. Siga los pasos a continuación para resolver el problema dado.  

• Cree una array máxima que calcule el elemento máximo a la izquierda hasta ese índice de la array.
• Cree una array mínima que calcule el elemento mínimo a la derecha hasta ese índice de la array.
• Iterar a través de la array, cada vez que todos los elementos a la izquierdaMax[] son ​​más pequeños (o iguales) a todos los elementos a la derechaMax[] , eso significa que hay un nuevo fragmento, así que incremente el conteo en 1 .
• Devuelve count+1 como respuesta final.

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum partitions.
int maxPartitions(vector<int>& arr)
{
    int N = arr.size();
 
    // To keep track of max
    // and min elements at every index
    vector<int> leftMax(arr.size());
    vector<int> rightMin(arr.size());
 
    leftMax[0] = arr[0];
 
    for (int i = 1; i < N; i++) {
        leftMax[i] = max(leftMax[i - 1],
                         arr[i]);
    }
 
    rightMin[N - 1] = arr[N - 1];
 
    for (int i = N - 2; i >= 0; i--) {
        rightMin[i] = min(rightMin[i + 1],
                          arr[i]);
    }
 
    int count = 0;
 
    for (int i = 0; i < N - 1; i++) {
        if (leftMax[i] <= rightMin[i + 1]) {
            count++;
        }
    }
 
    // Return count + 1 as the final answer
    return count + 1;
}
 
// Driver code
int main()
{
    vector<int> arr{ 10, 0, 21, 32, 68 };
 
    cout << maxPartitions(arr);
    return 0;
}

// Java implementation of the above approach
import java.util.*;
public class GFG {
 
  // Function to find maximum partitions.
  static int maxPartitions(int[] arr)
  {
    int N = arr.length;
 
    // To keep track of max
    // and min elements at every index
    int[] leftMax = new int[arr.length];
    int[] rightMin = new int[arr.length];
 
    leftMax[0] = arr[0];
 
    for (int i = 1; i < N; i++) {
      leftMax[i] = Math.max(leftMax[i - 1], arr[i]);
    }
 
    rightMin[N - 1] = arr[N - 1];
 
    for (int i = N - 2; i >= 0; i--) {
      rightMin[i] = Math.min(rightMin[i + 1], arr[i]);
    }
 
    int count = 0;
 
    for (int i = 0; i < N - 1; i++) {
      if (leftMax[i] <= rightMin[i + 1]) {
        count++;
      }
    }
 
    // Return count + 1 as the final answer
    return count + 1;
  }
 
  // Driver code
  public static void main(String args[])
  {
    int[] arr = { 10, 0, 21, 32, 68 };
 
    System.out.println(maxPartitions(arr));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

# Python program for above approach
 
# Function to find maximum partitions.
def maxPartitions(arr):
    N = len(arr)
 
    # To keep track of max
    # and min elements at every index
    leftMax = []
    rightMin = []
 
    leftMax.append(arr[0])
 
    for i in range(1, N):
        leftMax.append(max(leftMax[i - 1], arr[i]))
 
    rightMin.append(arr[N - 1])
 
    for i in range(1, N):
        rightMin.append(min(rightMin[i - 1], arr[N - i - 1]))
    rightMin.reverse()
    count = 0
 
    for i in range(0, N - 1):
        if (leftMax[i] <= rightMin[i + 1]):
            count = count + 1
 
    # Return count + 1 as the final answer
    return count + 1
 
# Driver code
arr = [10, 0, 21, 32, 68]
print(maxPartitions(arr))
 
# This code is contributed by Samim Hossain Mondal.

// C# program for above approach
using System;
class GFG {
 
  // Function to find maximum partitions.
  static int maxPartitions(int[] arr)
  {
    int N = arr.Length;
 
    // To keep track of max
    // and min elements at every index
    int[] leftMax = new int[arr.Length];
    int[] rightMin = new int[arr.Length];
 
    leftMax[0] = arr[0];
 
    for (int i = 1; i < N; i++) {
      leftMax[i] = Math.Max(leftMax[i - 1], arr[i]);
    }
 
    rightMin[N - 1] = arr[N - 1];
 
    for (int i = N - 2; i >= 0; i--) {
      rightMin[i] = Math.Min(rightMin[i + 1], arr[i]);
    }
 
    int count = 0;
 
    for (int i = 0; i < N - 1; i++) {
      if (leftMax[i] <= rightMin[i + 1]) {
        count++;
      }
    }
 
    // Return count + 1 as the final answer
    return count + 1;
  }
 
  // Driver code
  public static void Main()
  {
    int[] arr = { 10, 0, 21, 32, 68 };
 
    Console.WriteLine(maxPartitions(arr));
  }
}
 
// This code is contributed by ukasp.

<script>
       // JavaScript code for the above approach
 
       // Function to find maximum partitions.
       function maxPartitions(arr)
       {
           let N = arr.length;
 
           // To keep track of max
           // and min elements at every index
           let leftMax = new Array(arr.length);
           let rightMin = new Array(arr.length);
 
           leftMax[0] = arr[0];
 
           for (let i = 1; i < N; i++) {
               leftMax[i] = Math.max(leftMax[i - 1],
                   arr[i]);
           }
 
           rightMin[N - 1] = arr[N - 1];
 
           for (let i = N - 2; i >= 0; i--) {
               rightMin[i] = Math.min(rightMin[i + 1],
                   arr[i]);
           }
 
           let count = 0;
 
           for (let i = 0; i < N - 1; i++) {
               if (leftMax[i] <= rightMin[i + 1]) {
                   count++;
               }
           }
 
           // Return count + 1 as the final answer
           return count + 1;
       }
 
       // Driver code
       let arr = [10, 0, 21, 32, 68];
       document.write(maxPartitions(arr));
 
        // This code is contributed by Potta Lokesh
   </script>

4

Complejidad temporal : O(N)
Espacio auxiliar: O(N)