Divida la array en subarreglos máximos de modo que cada elemento distinto se encuentre en un solo subarreglo

Dada una array , arr[] de tamaño N , la tarea es dividir la array en el número máximo de subarreglos de manera que la primera y la última aparición de todos los elementos de array distintos se encuentren en un solo subarreglo.

Ejemplos:

Entrada: arr[] = {1, 1, 2, 2}
Salida: 2
Explicación:
Divida la array en subarreglos {1, 1} y {2, 2}.
Por lo tanto, la salida requerida es 2.

Entrada: arr[] = {1, 2, 4, 1, 4, 7, 7, 8}
Salida: 3
Explicación:
Divida la array en subarreglos {1, 2, 4, 1, 4}, {7, 7} y {8}.
Por lo tanto, la salida requerida es 3.

Enfoque: la idea es usar Hashing para almacenar el índice de la última aparición de cada elemento de la array. Siga los pasos a continuación para resolver el problema:

1. Inicialice una array, digamos hash[] para almacenar el índice de la última aparición de cada elemento de la array .
2. Atraviese la array y verifique si el índice máximo de la última aparición de todos los elementos anteriores de la array actual es menor o igual que el índice actual, luego incremente la cuenta en 1.
3. Finalmente, imprima el valor de count .

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

// C++ program to implement
// the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
// Function to maximize the
// count of subarrays
int maxCtSubarrays(int arr[], int N)
{
    // Store the last index of
    // every array element
    int hash[1000001] = { 0 };
  
    for (int i = 0; i < N; i++) {
        hash[arr[i]] = i;
    }
  
    // Store the maximum index of the
    // last occurrence of all elements
    int maxIndex = -1;
  
    // Store the count of subarrays
    int res = 0;
  
    for (int i = 0; i < N; i++) {
        maxIndex = max(maxIndex,
                       hash[arr[i]]);
  
        // If maximum of last indices
        // previous elements is equal
        // to the current index
        if (maxIndex == i) {
            res++;
        }
    }
  
    // Return the count
    // of subarrays
    return res;
}
  
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 1,
                  4, 7, 7, 8 };
    int N = sizeof(arr)
            / sizeof(arr[0]);
  
    cout << maxCtSubarrays(arr, N);
}

// Java program to implement
// the above approach
import java.util.*;
class GFG {
  
// Function to maximize the
// count of subarrays
static int maxCtSubarrays(int arr[], 
                          int N)
{
  // Store the last index of
  // every array element
  int hash[] = new int[1000001];
  
  for (int i = 0; i < N; i++) 
  {
    hash[arr[i]] = i;
  }
  
  // Store the maximum index of the
  // last occurrence of all elements
  int maxIndex = -1;
  
  // Store the count of subarrays
  int res = 0;
  
  for (int i = 0; i < N; i++) 
  {
    maxIndex = Math.max(maxIndex, 
                        hash[arr[i]]);
  
    // If maximum of last indices
    // previous elements is equal
    // to the current index
    if (maxIndex == i) 
    {
      res++;
    }
  }
  
  // Return the count
  // of subarrays
  return res;
}
  
// Driver Code
public static void main(String[] args)
{
  int arr[] = {1, 2, 4, 1, 
               4, 7, 7, 8};
  int N = arr.length;
  System.out.print(maxCtSubarrays(arr, N));
}
}
  
// This code is contributed by Chitranayal

# Python3 program to implement
# the above approach
  
# Function to maximize the
# count of subarrays
def maxCtSubarrays(arr, N):
      
    # Store the last index of
    # every array element
    hash = [0] * (1000001)
  
    for i in range(N):
        hash[arr[i]] = i
  
    # Store the maximum index of the
    # last occurrence of all elements
    maxIndex = -1
  
    # Store the count of subarrays
    res = 0
  
    for i in range(N):
        maxIndex = max(maxIndex,
                       hash[arr[i]])
  
        # If maximum of last indices
        # previous elements is equal
        # to the current index
        if (maxIndex == i):
            res += 1
  
    # Return the count
    # of subarrays
    return res
  
# Driver Code
if __name__ == '__main__':
      
    arr = [ 1, 2, 4, 1,
            4, 7, 7, 8 ]
    N = len(arr)
  
    print(maxCtSubarrays(arr, N))
  
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG {
  
// Function to maximize the
// count of subarrays
static int maxCtSubarrays(int []arr, 
                          int N)
{
  // Store the last index of
  // every array element
  int []hash = new int[1000001];
  
  for (int i = 0; i < N; i++) 
  {
    hash[arr[i]] = i;
  }
  
  // Store the maximum index of the
  // last occurrence of all elements
  int maxIndex = -1;
  
  // Store the count of subarrays
  int res = 0;
  
  for (int i = 0; i < N; i++) 
  {
    maxIndex = Math.Max(maxIndex, 
                        hash[arr[i]]);
  
    // If maximum of last indices
    // previous elements is equal
    // to the current index
    if (maxIndex == i) 
    {
      res++;
    }
  }
  
  // Return the count
  // of subarrays
  return res;
}
  
// Driver Code
public static void Main(String[] args)
{
  int []arr = {1, 2, 4, 1, 
               4, 7, 7, 8};
  int N = arr.Length;
  Console.Write(maxCtSubarrays(arr, N));
}
}
  
// This code is contributed by Princi Singh

<script>
  
// Javascript program to implement
// the above approach
    
// Function to maximize the
// count of subarrays
function maxCtSubarrays(arr, N)
{
  // Store the last index of
  // every array element
  let hash = new Array(1000001).fill(0); 
   
  for (let i = 0; i < N; i++)
  {
    hash[arr[i]] = i;
  }
   
  // Store the maximum index of the
  // last occurrence of all elements
  let maxIndex = -1;
   
  // Store the count of subarrays
  let res = 0;
   
  for (let i = 0; i < N; i++)
  {
    maxIndex = Math.max(maxIndex,
                        hash[arr[i]]);
   
    // If maximum of last indices
    // previous elements is equal
    // to the current index
    if (maxIndex == i)
    {
      res++;
    }
  }
   
  // Return the count
  // of subarrays
  return res;
}
  
// Driver Code
  
        let arr = [1, 2, 4, 1,
               4, 7, 7, 8];
          let N = arr.length;
          document.write(maxCtSubarrays(arr, N));
  
// This code is contributed by avijitmondal1998.
</script>

3

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(X) donde X, es el elemento máximo en el arreglo dado.

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array