Dado un arreglo arr[], la tarea es encontrar la longitud del subarreglo alterno más largo.
Un subarreglo {x1, x2, .. xn} es una secuencia alterna creciente decreciente si sus elementos satisfacen una de las siguientes relaciones:
x1 < x2 > x3 < x4 > x5 < …. xn o
x1 > x2 < x3 > x4 < x5 > …. xn
Ejemplo:
Entrada: arr = {1, 2, 3, 2, 5, 6}
Salida: 4
Explicación: Los primeros elementos del índice 1 a 4 inclusive son subarreglos alternos: {2, 3, 2, 5}Entrada: arr = {5, 2, 1}
Salida: 2
Enfoque ingenuo: el enfoque ingenuo consiste en verificar para cada subarreglo si los subarreglos que comienzan en cada índice se alternan. La idea es utilizar dos bucles for anidados.
A continuación se muestra la implementación del enfoque anterior.
C++14
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
int maxAlternatingSubarray(int n, int* arr)
{
// Initialize mx to store maximum
// length alternating subarrays
int i, j, max = 1, count = 1, a, b;
// Initialize a variable to check is the
// subarray starts with greater
// or smaller value
bool check;
// If length of the array is 1
// then return 1
if (n == 1)
return 1;
// Traverse for every element
for (i = 0; i < n; i++) {
// Reintialize count to 1 as
// at least one element is counted
count = 1;
// Subarray starting at every element
for (j = i; j < n - 1; j++) {
// Initialize a and b for storing
// adjacent positions
a = j;
b = j + 1;
// Check if the alternating subarray
// starts with greater
// or smaller element
if (j == i) {
// Smaller element starts first
if (arr[a] < arr[b])
check = 1;
// Greater element starts first
else if (arr[a] > arr[b])
check = 0;
}
// If check is 1 then the next
// element should be greater
if (check && arr[a] < arr[b]) {
// Increment count
count++;
}
// If check is 0 then the next
// element should be greater
else if (!check && arr[a] > arr[b]) {
// Increment count
count++;
}
else
break;
// Update the value of check
check = !check;
}
// Update the maximum value of count
if (max < count)
max = count;
}
// Return the maximum length
return max;
}
// Driver code
int main()
{
// Initialize the array
int arr[] = { 1, 2, 3, 2, 5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Call the function and print the answer
cout << maxAlternatingSubarray(n, arr);
}
Java
// Java code for the above approach
import java.io.*;
class GFG {
static int maxAlternatingSubarray(int n, int[] arr)
{
// Initialize mx to store maximum
// length alternating subarrays
int i, j, max = 1, count = 1, a, b;
// Initialize a variable to check is the
// subarray starts with greater
// or smaller value
boolean check=false;
// If length of the array is 1
// then return 1
if (n == 1)
return 1;
// Traverse for every element
for (i = 0; i < n; i++) {
// Reintialize count to 1 as
// at least one element is counted
count = 1;
// Subarray starting at every element
for (j = i; j < n - 1; j++) {
// Initialize a and b for storing
// adjacent positions
a = j;
b = j + 1;
// Check if the alternating subarray
// starts with greater
// or smaller element
if (j == i) {
// Smaller element starts first
if (arr[a] < arr[b])
check = true;
// Greater element starts first
else if (arr[a] > arr[b])
check = false;
}
// If check is 1 then the next
// element should be greater
if (check==true && arr[a] < arr[b]) {
// Increment count
count++;
}
// If check is 0 then the next
// element should be greater
else if (check==false && arr[a] > arr[b]) {
// Increment count
count++;
}
else
break;
// Update the value of check
check = !check;
}
// Update the maximum value of count
if (max < count)
max = count;
}
// Return the maximum length
return max;
}
// Driver code
public static void main (String[] args)
{
// Initialize the array
int arr[] = { 1, 2, 3, 2, 5, 7 };
int n = arr.length;
// Call the function and print the answer
System.out.println( maxAlternatingSubarray(n, arr));
}
}
// This code is contributed by Potta Lokesh
Python3
# Python implementation of the above approach def maxAlternatingSubarray(n, arr): # Initialize mx to store maximum # length alternating subarrays max = 1 count = 1 a = 0 b = 0 # Initialize a variable to check is the # subarray starts with greater # or smaller value check = 0 # If length of the array is 1 # then return 1 if (n == 1): return 1; # Traverse for every element for i in range(n): # Reintialize count to 1 as # at least one element is counted count = 1; # Subarray starting at every element for j in range(i, n - 1): # Initialize a and b for storing # adjacent positions a = j; b = j + 1; # Check if the alternating subarray # starts with greater # or smaller element if (j == i): # Smaller element starts first if (arr[a] < arr[b]): check = 1; # Greater element starts first elif (arr[a] > arr[b]): check = 0; # If check is 1 then the next # element should be greater if (check and arr[a] < arr[b]): # Increment count count += 1 # If check is 0 then the next # element should be greater elif (not check and arr[a] > arr[b]): # Increment count count += 1 else: break; # Update the value of check check = not check; # Update the maximum value of count if (max < count): max = count; # Return the maximum length return max; # Driver code # Initialize the array arr = [ 1, 2, 3, 2, 5, 7 ]; n = len(arr); # Call the function and print the answer print(maxAlternatingSubarray(n, arr)); # This code is contributed by gfgking.
C#
// C# code for the above approach
using System;
class GFG {
static int maxAlternatingSubarray(int n, int []arr)
{
// Initialize mx to store maximum
// length alternating subarrays
int i, j, max = 1, count = 1, a, b;
// Initialize a variable to check is the
// subarray starts with greater
// or smaller value
bool check=false;
// If length of the array is 1
// then return 1
if (n == 1)
return 1;
// Traverse for every element
for (i = 0; i < n; i++) {
// Reintialize count to 1 as
// at least one element is counted
count = 1;
// Subarray starting at every element
for (j = i; j < n - 1; j++) {
// Initialize a and b for storing
// adjacent positions
a = j;
b = j + 1;
// Check if the alternating subarray
// starts with greater
// or smaller element
if (j == i) {
// Smaller element starts first
if (arr[a] < arr[b])
check = true;
// Greater element starts first
else if (arr[a] > arr[b])
check = false;
}
// If check is 1 then the next
// element should be greater
if (check==true && arr[a] < arr[b]) {
// Increment count
count++;
}
// If check is 0 then the next
// element should be greater
else if (check==false && arr[a] > arr[b]) {
// Increment count
count++;
}
else
break;
// Update the value of check
check = !check;
}
// Update the maximum value of count
if (max < count)
max = count;
}
// Return the maximum length
return max;
}
// Driver code
public static void Main ()
{
// Initialize the array
int []arr = { 1, 2, 3, 2, 5, 7 };
int n = arr.Length;
// Call the function and print the answer
Console.Write(maxAlternatingSubarray(n, arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation of the above approach
function maxAlternatingSubarray(n, arr)
{
// Initialize mx to store maximum
// length alternating subarrays
let i, j, max = 1, count = 1, a, b;
// Initialize a variable to check is the
// subarray starts with greater
// or smaller value
let check;
// If length of the array is 1
// then return 1
if (n == 1)
return 1;
// Traverse for every element
for (i = 0; i < n; i++) {
// Reintialize count to 1 as
// at least one element is counted
count = 1;
// Subarray starting at every element
for (j = i; j < n - 1; j++) {
// Initialize a and b for storing
// adjacent positions
a = j;
b = j + 1;
// Check if the alternating subarray
// starts with greater
// or smaller element
if (j == i) {
// Smaller element starts first
if (arr[a] < arr[b])
check = 1;
// Greater element starts first
else if (arr[a] > arr[b])
check = 0;
}
// If check is 1 then the next
// element should be greater
if (check && arr[a] < arr[b]) {
// Increment count
count++;
}
// If check is 0 then the next
// element should be greater
else if (!check && arr[a] > arr[b]) {
// Increment count
count++;
}
else
break;
// Update the value of check
check = !check;
}
// Update the maximum value of count
if (max < count)
max = count;
}
// Return the maximum length
return max;
}
// Driver code
// Initialize the array
let arr = [ 1, 2, 3, 2, 5, 7 ];
let n = arr.length;
// Call the function and print the answer
document.write(maxAlternatingSubarray(n, arr));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción:
4
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Enfoque: el problema dado se puede optimizar iterando la array y calculando previamente la diferencia entre elementos consecutivos. Siga los pasos a continuación para resolver el problema:
- Itere la array desde el índice 1 hasta el final y en cada iteración:
- Si el elemento actual es mayor que el elemento anterior, incremente currGreater en 1 y restablezca currSmaller a 0
- De lo contrario, si el elemento actual es más pequeño que el elemento anterior, incremente currSmaller en 1 y restablezca currGreater a 0
- De lo contrario, si los elementos actuales y anteriores son iguales, restablezca tanto currGreater como currSmaller a 0
- Intercambiar los valores de currGreater y currSmaller
- Actualice el valor de la longitud máxima comparándolo con currGreater y currSmaller
- Devuelve el valor de la longitud máxima calculada
C++14
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum length
// of alternating subarray
int longestAltSubarray(int N, int* arr)
{
// If length of the array is 1
// then return 1
if (N == 1)
return 1;
int maxLen = 0;
int currGreater = 0, currSmaller = 0;
// Traverse the temp array
for (int i = 1; i < N; i++) {
// If current element is greater
// than the previous element
if (arr[i] > arr[i - 1]) {
// Increment currGreater by 1
currGreater++;
// Reset currSmaller to 0
currSmaller = 0;
}
// If current element is smaller
// than the previous element
else if (arr[i] < arr[i - 1]) {
// Increment currSmaller by 1
currSmaller++;
// Reset currGreater to 0
currGreater = 0;
}
// If current element is equal
// to previous element
else {
// Reset both to 0
currGreater = 0;
currSmaller = 0;
}
// Swap currGreater and currSmaller
// for the next iteration
int temp = currGreater;
currGreater = currSmaller;
currSmaller = temp;
// Update maxLen
maxLen = max(maxLen,
max(currGreater, currSmaller));
}
// Return the maximum length
return maxLen + 1;
}
// Drivers code
int main()
{
// Initialize the array
int arr[] = { 1, 2, 3, 2, 5, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Call the function and print the answer
cout << longestAltSubarray(n, arr);
}
Java
// Java implementation for the above approach
import java.util.*;
public class GFG
{
// Function to calculate maximum length
// of alternating subarray
static int longestAltSubarray(int N, int []arr)
{
// If length of the array is 1
// then return 1
if (N == 1)
return 1;
int maxLen = 0;
int currGreater = 0, currSmaller = 0;
// Traverse the temp array
for (int i = 1; i < N; i++) {
// If current element is greater
// than the previous element
if (arr[i] > arr[i - 1]) {
// Increment currGreater by 1
currGreater++;
// Reset currSmaller to 0
currSmaller = 0;
}
// If current element is smaller
// than the previous element
else if (arr[i] < arr[i - 1]) {
// Increment currSmaller by 1
currSmaller++;
// Reset currGreater to 0
currGreater = 0;
}
// If current element is equal
// to previous element
else {
// Reset both to 0
currGreater = 0;
currSmaller = 0;
}
// Swap currGreater and currSmaller
// for the next iteration
int temp = currGreater;
currGreater = currSmaller;
currSmaller = temp;
// Update maxLen
maxLen = Math.max(maxLen,
Math.max(currGreater, currSmaller));
}
// Return the maximum length
return maxLen + 1;
}
// Drivers code
public static void main(String args[])
{
// Initialize the array
int []arr = { 1, 2, 3, 2, 5, 7 };
int n = arr.length;
// Call the function and print the answer
System.out.println(longestAltSubarray(n, arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python3 implementation for the above approach from builtins import range # Function to calculate maximum length # of alternating subarray def longestAltSubarray(N, arr): # If length of the array is 1 # then return 1 if (N == 1): return 1 maxLen = 0 currGreater = 0 currSmaller = 0 # Traverse the temp array for i in range(1, N, 1): # If current element is greater # than the previous element if (arr[i] > arr[i - 1]): # Increment currGreater by 1 currGreater += 1 # Reset currSmaller to 0 currSmaller = 0 # If current element is smaller # than the previous element elif (arr[i] < arr[i - 1]): # Increment currSmaller by 1 currSmaller += 1 # Reset currGreater to 0 currGreater = 0 # If current element is equal # to previous element else: # Reset both to 0 currGreater = 0 currSmaller = 0 # Swap currGreater and currSmaller # for the next iteration temp = currGreater currGreater = currSmaller currSmaller = temp # Update maxLen maxLen = max(maxLen, max(currGreater, currSmaller)) # Return the maximum length return maxLen + 1 # Driver code if __name__ == '__main__': # Initialize the array arr = [ 1, 2, 3, 2, 5, 7 ] n = len(arr) # Call the function and print the answer print(longestAltSubarray(n, arr)) # This code is contributed by shikhasingrajput
C#
// C# implementation for the above approach
using System;
class GFG
{
// Function to calculate maximum length
// of alternating subarray
static int longestAltSubarray(int N, int []arr)
{
// If length of the array is 1
// then return 1
if (N == 1)
return 1;
int maxLen = 0;
int currGreater = 0, currSmaller = 0;
// Traverse the temp array
for (int i = 1; i < N; i++) {
// If current element is greater
// than the previous element
if (arr[i] > arr[i - 1]) {
// Increment currGreater by 1
currGreater++;
// Reset currSmaller to 0
currSmaller = 0;
}
// If current element is smaller
// than the previous element
else if (arr[i] < arr[i - 1]) {
// Increment currSmaller by 1
currSmaller++;
// Reset currGreater to 0
currGreater = 0;
}
// If current element is equal
// to previous element
else {
// Reset both to 0
currGreater = 0;
currSmaller = 0;
}
// Swap currGreater and currSmaller
// for the next iteration
int temp = currGreater;
currGreater = currSmaller;
currSmaller = temp;
// Update maxLen
maxLen = Math.Max(maxLen,
Math.Max(currGreater, currSmaller));
}
// Return the maximum length
return maxLen + 1;
}
// Drivers code
public static void Main()
{
// Initialize the array
int []arr = { 1, 2, 3, 2, 5, 7 };
int n = arr.Length;
// Call the function and print the answer
Console.Write(longestAltSubarray(n, arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript implementation for the above approach
// Function to calculate maximum length
// of alternating subarray
function longestAltSubarray(N, arr) {
// If length of the array is 1
// then return 1
if (N == 1)
return 1;
let maxLen = 0;
let currGreater = 0, currSmaller = 0;
// Traverse the temp array
for (let i = 1; i < N; i++) {
// If current element is greater
// than the previous element
if (arr[i] > arr[i - 1]) {
// Increment currGreater by 1
currGreater++;
// Reset currSmaller to 0
currSmaller = 0;
}
// If current element is smaller
// than the previous element
else if (arr[i] < arr[i - 1]) {
// Increment currSmaller by 1
currSmaller++;
// Reset currGreater to 0
currGreater = 0;
}
// If current element is equal
// to previous element
else {
// Reset both to 0
currGreater = 0;
currSmaller = 0;
}
// Swap currGreater and currSmaller
// for the next iteration
let temp = currGreater;
currGreater = currSmaller;
currSmaller = temp;
// Update maxLen
maxLen = Math.max(maxLen,
Math.max(currGreater, currSmaller));
}
// Return the maximum length
return maxLen + 1;
}
// Drivers code
// Initialize the array
let arr = [1, 2, 3, 2, 5, 7];
let n = arr.length
// Call the function and let the answer
document.write(longestAltSubarray(n, arr))
// This code is contributed by gfgking.
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA