Dividir una array en un número mínimo de subarreglos no crecientes o no decrecientes

Dada una array arr[] de tamaño N , la tarea es dividir la array dada en un número mínimo de subarreglos de modo que los elementos de cada subarreglo estén en orden no creciente o no decreciente.

Ejemplos:

Entrada: arr[] = {2, 3, 9, 5, 4, 6, 8}
Salida: 3
Explicación: Divida la array en 3 subarreglos siguiendo tres subarreglos: 

  1. {2, 3, 9} (no decreciente)
  2. {5, 4} (no creciente)
  3. {6, 8} (no decreciente)

Entrada: arr[] = {2, 5, 3, 3, 4, 5, 0, 2, 1, 0} 
Salida: 4
Explicación: Divida la array en los siguientes 4 subarreglos: 

  1. {2, 5} (no decreciente)
  2. {3, 3, 4, 5} (no decreciente)
  3. {0, 2} (no decreciente)
  4. {1, 0} (no creciente)

Enfoque: para minimizar el número de subarreglos, se debe maximizar el tamaño de cada subarreglo. Se puede hacer colocando los elementos en subarreglos con avidez. 

Siga los pasos a continuación para resolver el problema:

  • Inicialice una variable, digamos ans , con 1 para almacenar el resultado requerido y actualice con N para realizar un seguimiento del orden de la secuencia actual, ya sea no decreciente (I) , no creciente (D) o ninguno (N ) .
  • Ahora, itere sobre la array en el rango [1, N – 1] :
    • Si la corriente es igual a N , haga lo siguiente: 
      • Si arr[i] < arr[i-1] entonces actualice actual como D .
      • De lo contrario, si arr[i] > arr[i-1] , actualice actual como I .
      • De lo contrario, actualice actual como N .
    • Si la corriente es igual a I , haga lo siguiente:
      • Si arr[i]≥arr[i-1] entonces actualice actual como I .
      • De lo contrario, actualice la corriente como N e incremente ans en 1 .
    • De lo contrario, haga lo siguiente:
      • Si arr[i] ≤ arr[i-1] , actualice actual como D .
      • De lo contrario, actualice la corriente como N e incremente ans en 1 .
  • Después de los pasos anteriores, imprima el valor de ans como resultado.

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

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to split the array into minimum count
// of subarrays such that each subarray is either
// non-increasing or non-decreasing
void minimumSubarrays(int arr[], int n)
{
 
  // Initialize variable to keep
  // track of current sequence
  char current = 'N';
 
  // Stores the required result
  int answer = 1;
 
  // Traverse the array, arr[]
  for (int i = 1; i < n; i++) {
 
    // If current sequence is neither
    // non-increasing nor non-decreasing
    if (current == 'N') {
 
      // If previous element is greater
      if (arr[i] < arr[i - 1]) {
 
        // Update current
        current = 'D';
      }
 
      // If previous element is equal
      // to the current element
      else if (arr[i] == arr[i - 1]) {
 
        // Update current
        current = 'N';
      }
 
      // Otherwise
      else {
 
        // Update current
        current = 'I';
      }
    }
 
    // If current sequence
    // is in non-decreasing
    else if (current == 'I') {
 
      // If previous element is
      // less than or equal to
      // the current element
      if (arr[i] >= arr[i - 1]) {
        current = 'I';
      }
 
      // Otherwise
      else {
 
        // Update current as N and
        // increment answer by 1
        current = 'N';
        answer += 1;
      }
    }
 
    // If current sequence
    // is Non-Increasing
    else {
 
      // If previous element is
      // greater or equal to
      // the current element
      if (arr[i] <= arr[i - 1]) {
        current = 'D';
      }
 
      // Otherwise
      else {
 
        // Update current as N and
        // increment answer by 1
        current = 'N';
        answer += 1;
      }
    }
  }
 
  // Print the answer
  cout<<answer;
}
 
// Driver Code
int main() {
 
  // Given array
  int arr[] = { 2, 3, 9, 5, 4, 6, 8 };
 
  // Given size of array
  int n = sizeof(arr) / sizeof(arr[0]);
 
  minimumSubarrays(arr, n);
  return 0;
}
 
// This code is contributed by shikhasingrajput

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    static void minimumSubarrays(int[] arr, int n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        char current = 'N';
 
        // Stores the required result
        int answer = 1;
 
        // Traverse the array, arr[]
        for (int i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        System.out.print(answer);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array
        int arr[] = { 2, 3, 9, 5, 4, 6, 8 };
 
        // Given size of array
        int n = arr.length;
 
        minimumSubarrays(arr, n);
    }
}

Python3

# Python3 program for the above approach
 
# Function to split the array into minimum count
# of subarrays such that each subarray is either
# non-increasing or non-decreasing
def minimumSubarrays(arr, n):
 
    # Initialize variable to keep
    # track of current sequence
    current = 'N'
 
    # Stores the required result
    answer = 1
 
    # Traverse the array, arr[]
    for i in range(1, n):
 
        # If current sequence is neither
        # non-increasing nor non-decreasing
        if (current == 'N'):
 
            # If previous element is greater
            if (arr[i] < arr[i - 1]):
 
                # Update current
                current = 'D'
 
            # If previous element is equal
            # to the current element
            elif (arr[i] == arr[i - 1]):
 
                # Update current
                current = 'N'
 
            # Otherwise
            else:
 
                # Update current
                current = 'I'
 
        # If current sequence
        # is in non-decreasing
        elif (current == 'I'):
 
            #I f previous element is
            # less than or equal to
            # the current element
            if (arr[i] >= arr[i - 1]):
                current = 'I'
 
            # Otherwise
            else:
 
                # Update current as N and
                # increment answer by 1
                current = 'N'
                answer += 1
 
        # If current sequence
        # is Non-Increasing
        else:
 
            # If previous element is
            # greater or equal to
            # the current element
            if (arr[i] <= arr[i - 1]):
                current = 'D'
 
            # Otherwise
            else:
 
                # Update current as N and
                # increment answer by 1
                current = 'N'
                answer += 1
 
    # Print the answer
    print(answer)
 
# Driver Code
if __name__ == '__main__':
 
    # Given array
    arr = [ 2, 3, 9, 5, 4, 6, 8 ]
 
    # Given size of array
    n = len(arr)
     
    minimumSubarrays(arr, n)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    static void minimumSubarrays(int[] arr, int n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        char current = 'N';
 
        // Stores the required result
        int answer = 1;
 
        // Traverse the array, []arr
        for (int i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        Console.Write(answer);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
 
        // Given array
        int []arr = { 2, 3, 9, 5, 4, 6, 8 };
 
        // Given size of array
        int n = arr.Length;
 
        minimumSubarrays(arr, n);
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Java script program for the above approach
 
 
 
    // Function to split the array into minimum count
    // of subarrays such that each subarray is either
    // non-increasing or non-decreasing
    function minimumSubarrays(arr,n)
    {
 
        // Initialize variable to keep
        // track of current sequence
        let current = 'N';
 
        // Stores the required result
        let answer = 1;
 
        // Traverse the array, arr[]
        for (let i = 1; i < n; i++) {
 
            // If current sequence is neither
            // non-increasing nor non-decreasing
            if (current == 'N') {
 
                // If previous element is greater
                if (arr[i] < arr[i - 1]) {
 
                    // Update current
                    current = 'D';
                }
 
                // If previous element is equal
                // to the current element
                else if (arr[i] == arr[i - 1]) {
 
                    // Update current
                    current = 'N';
                }
 
                // Otherwise
                else {
 
                    // Update current
                    current = 'I';
                }
            }
 
            // If current sequence
            // is in non-decreasing
            else if (current == 'I') {
 
                // If previous element is
                // less than or equal to
                // the current element
                if (arr[i] >= arr[i - 1]) {
                    current = 'I';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
 
            // If current sequence
            // is Non-Increasing
            else {
 
                // If previous element is
                // greater or equal to
                // the current element
                if (arr[i] <= arr[i - 1]) {
                    current = 'D';
                }
 
                // Otherwise
                else {
 
                    // Update current as N and
                    // increment answer by 1
                    current = 'N';
                    answer += 1;
                }
            }
        }
 
        // Print the answer
        document.write(answer);
    }
 
    // Driver Code
     
        // Given array
        let arr = [ 2, 3, 9, 5, 4, 6, 8 ];
 
        // Given size of array
        let n = arr.length;
 
        minimumSubarrays(arr, n);
 
// contributed by sravan kumar
</script>
Producción: 

3

 

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

Publicación traducida automáticamente

Artículo escrito por kunalsg18elec y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *