Número máximo de particiones que se pueden ordenar individualmente para ordenar

Dada una array arr[] de tamaño n tal que los elementos de arr[] en el rango [0, 1, ..n-1] donde cada número está presente como máximo una vez. Nuestra tarea es dividir la array en el número máximo de particiones que se pueden ordenar individualmente y luego concatenar para ordenar toda la array.
Ejemplos: 

Input : arr[] = [2, 1, 0, 3]
Output : 2
If divide arr[] into two partitions
{2, 1, 0} and {3}, sort then and concatenate
then, we get the whole array sorted.

Input : arr[] = [2, 1, 0, 3, 4, 5]
Output : 4
The maximum number of partitions are four, we
get these partitions as {2, 1, 0}, {3}, {4} 
and {5}

Input : arr[] = [0, 1, 2, 3, 4, 5]
Output : 6
The maximum number of partitions are six, we
get these partitions as {0}, {1}, {2}, {3}, {4} 
and {5}

La idea se basa en el hecho de que si un elemento en i es el máximo del prefijo arr[0..i], entonces podemos hacer una partición que termine en i.  

// CPP program to find Maximum number of partitions such
// that we can get a sorted array.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum partitions.
int maxPartitions(int arr[], int n)
{
    int ans = 0, max_so_far = 0;
    for (int i = 0; i < n; ++i) {
 
        // Find maximum in prefix arr[0..i]
        max_so_far = max(max_so_far, arr[i]);
 
        // If maximum so far is equal to index, we can make
        // a new partition ending at index i.
        if (max_so_far == i)
            ans++;
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 0, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << maxPartitions(arr, n);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// C program to find Maximum number of partitions such that
// we can get a sorted array.
#include <stdio.h>
 
// Find maximum between two numbers.
int max(int num1, int num2)
{
    return (num1 > num2) ? num1 : num2;
}
 
// Function to find maximum partitions.
int maxPartitions(int arr[], int n)
{
    int ans = 0, max_so_far = 0;
    for (int i = 0; i < n; ++i) {
 
        // Find maximum in prefix arr[0..i]
        max_so_far = max(max_so_far, arr[i]);
 
        // If maximum so far is equal to index, we can make
        // a new partition ending at index i.
        if (max_so_far == i)
            ans++;
    }
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 0, 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", maxPartitions(arr, n));
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

// java program to find Maximum number of partitions such
// that we can get a sorted array
 
import java.io.*;
 
class GFG {
    // Function to find maximum partitions.
    static int maxPartitions(int arr[], int n)
    {
        int ans = 0, max_so_far = 0;
        for (int i = 0; i < n; ++i) {
 
            // Find maximum in prefix arr[0..i]
            max_so_far = Math.max(max_so_far, arr[i]);
 
            // If maximum so far is equal to index, we can
            // make a new partition ending at index i.
            if (max_so_far == i)
                ans++;
        }
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 0, 2, 3, 4 };
        int n = arr.length;
        System.out.println(maxPartitions(arr, n));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

# Python3 program to find Maximum
# number of partitions such that
# we can get a sorted array.
 
# Function to find maximum partitions.
def maxPartitions(arr, n):
 
    ans = 0; max_so_far = 0
    for i in range(0, n):
 
        # Find maximum in prefix arr[0..i]
        max_so_far = max(max_so_far, arr[i])
 
        # If maximum so far is equal to
        # index, we can make a new partition
        # ending at index i.
        if (max_so_far == i):
            ans += 1
     
    return ans
 
# Driver code
arr = [1, 0, 2, 3, 4]
n = len(arr)
print(maxPartitions(arr, n))
 
# This code is contributed by Smitha Dinesh Semwal.

// C# program to find Maximum number of partitions
// such that we can get a sorted array
using System;
 
class GFG
{
    // Function to find maximum partitions.
    static int maxPartitions(int []arr, int n)
    {
        int ans = 0, max_so_far = 0;
        for (int i = 0; i < n; ++i)
        {
     
            // Find maximum in prefix arr[0..i]
            max_so_far = Math.Max(max_so_far, arr[i]);
     
            // If maximum so far is equal to index,
            // we can make a new partition ending at
            // index i.
            if (max_so_far == i)
                ans++;
        }
        return ans;
    }
     
    // Driver code
    public static void Main ()
    {
        int []arr = { 1, 0, 2, 3, 4 };
        int n = arr.Length;
        Console.Write (maxPartitions(arr, n));
             
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to find Maximum
// number of partitions such
// that we can get a sorted array.
 
// Function to find maximum partitions.
function maxPartitions($arr, $n)
{
    $ans = 0;
    $max_so_far = 0;
    for ($i = 0; $i < $n; ++$i) {
 
        // Find maximum in prefix arr[0..i]
        $max_so_far = max($max_so_far, $arr[$i]);
 
        // If maximum so far is equal to index,
        // we can make a new partition ending at
        // index i.
        if ($max_so_far == $i)
            $ans++;
    }
    return $ans;
}
 
// Driver code
{
    $arr = array(1, 0, 2, 3, 4);
    $n = sizeof($arr) / sizeof($arr[0]);
    echo maxPartitions($arr, $n);
    return 0;
}
 
// This code is contributed by nitin mittal
?>

<script>
    // Javascript program to find Maximum number of partitions
    // such that we can get a sorted array.
     
    // Function to find maximum partitions.
    function maxPartitions(arr, n)
    {
        let ans = 0, max_so_far = 0;
        for (let i = 0; i < n; ++i) {
 
            // Find maximum in prefix arr[0..i]
            max_so_far = Math.max(max_so_far, arr[i]);
 
            // If maximum so far is equal to index,
            // we can make a new partition ending at
            // index i.
            if (max_so_far == i)
                ans++;
        }
        return ans;
    }
     
    let arr = [ 1, 0, 2, 3, 4 ];
    let n = arr.length;
    document.write(maxPartitions(arr, n));
     
    // This code is contributed by divyesh072019.
</script>

4

Complejidad de tiempo: O(N)

Complejidad espacial: O(1)