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:
- {2, 3, 9} (no decreciente)
- {5, 4} (no creciente)
- {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:
- {2, 5} (no decreciente)
- {3, 3, 4, 5} (no decreciente)
- {0, 2} (no decreciente)
- {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 .
- Si la corriente es igual a N , haga lo siguiente:
- 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