Dada una array arr[] de tamaño N y entero K . La tarea es encontrar el subarreglo más largo con la diferencia entre elementos adyacentes como K .
Ejemplos:
Entrada: arr[] = { 5, 5, 5, 10, 8, 6, 12, 13 }, K =1
Salida: {12, 13}
Explicación: Este es el subarreglo más largo con una diferencia entre adyacentes igual a 1.Entrada: arr[] = {4, 6, 8, 9, 8, 12, 14, 17, 15}, K = 2
Salida: {4, 6, 8}
Enfoque: Comenzando desde el primer elemento de la array, encuentre la primera sub-array válida y almacene su longitud y punto de inicio. Luego, a partir del siguiente elemento (el primer elemento que no se incluyó en el primer subconjunto), busque otro subconjunto válido y continúe actualizando la longitud máxima y el punto de inicio . Repita el proceso hasta que se hayan encontrado todos los subconjuntos válidos y luego imprima el subconjunto de longitud máxima.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum length
// sub-array such that the
// absolute difference between every two
// consecutive elements is K
void getMaxLengthSubarray(int arr[],
int N, int K)
{
int l = N;
int i = 0, maxlen = 0;
int max_len_start, max_len_end;
while (i < l) {
int j = i;
while (i + 1 < l
&& (abs(arr[i]
- arr[i + 1]) == K)) {
i++;
}
// Length of the valid sub-array
// currently under consideration
int currLen = i - j + 1;
// Update the maximum length subarray
if (maxlen < currLen) {
maxlen = currLen;
max_len_start = j;
max_len_end = i;
}
if (j == i)
i++;
}
// Print the maximum length subarray
for (int p = max_len_start;
p <= max_len_end; p++)
cout << arr[p] << " ";
}
// Driver code
int main()
{
int arr[] = { 4, 6, 8, 9, 8, 12,
14, 17, 15 };
int K = 2;
int N = sizeof(arr) / sizeof(arr[0]);
getMaxLengthSubarray(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to return the maximum length
// sub-array such that the
// absolute difference between every two
// consecutive elements is K
static void getMaxLengthSubarray(int arr[],
int N, int K)
{
int l = N;
int i = 0, maxlen = 0;
int max_len_start = 0, max_len_end = 0;
while (i < l) {
int j = i;
while (i + 1 < l
&& (Math.abs(arr[i]
- arr[i + 1]) == K)) {
i++;
}
// Length of the valid sub-array
// currently under consideration
int currLen = i - j + 1;
// Update the maximum length subarray
if (maxlen < currLen) {
maxlen = currLen;
max_len_start = j;
max_len_end = i;
}
if (j == i)
i++;
}
// Print the maximum length subarray
for (int p = max_len_start;
p <= max_len_end; p++)
System.out.print(arr[p] + " ");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 4, 6, 8, 9, 8, 12,
14, 17, 15 };
int K = 2;
int N = arr.length;
getMaxLengthSubarray(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# Python program to implement # the above approach # Function to return the maximum length # sub-array such that the # absolute difference between every two # consecutive elements is K def getMaxLengthSubarray(arr, N, K) : l = N i = 0 maxlen = 0 while (i < l) : j = i while (i + 1 < l and (abs(arr[i] - arr[i + 1]) == K)) : i += 1 # Length of the valid sub-array # currently under consideration currLen = i - j + 1 # Update the maximum length subarray if (maxlen < currLen) : maxlen = currLen max_len_start = j max_len_end = i if (j == i) : i += 1 # Print the maximum length subarray for p in range(max_len_start, max_len_end+1, 1) : print(arr[p], end=" ") # Driver code arr = [ 4, 6, 8, 9, 8, 12, 14, 17, 15 ] K = 2 N = len(arr) getMaxLengthSubarray(arr, N, K) # This code is contributed by avijitmondal1998
C#
// C# program for the above approach
using System;
class GFG
{
// Function to return the maximum length
// sub-array such that the
// absolute difference between every two
// consecutive elements is K
static void getMaxLengthSubarray(int []arr,
int N, int K)
{
int l = N;
int i = 0, maxlen = 0;
int max_len_start = 0, max_len_end = 0;
while (i < l) {
int j = i;
while (i + 1 < l
&& (Math.Abs(arr[i]
- arr[i + 1]) == K)) {
i++;
}
// Length of the valid sub-array
// currently under consideration
int currLen = i - j + 1;
// Update the maximum length subarray
if (maxlen < currLen) {
maxlen = currLen;
max_len_start = j;
max_len_end = i;
}
if (j == i)
i++;
}
// Print the maximum length subarray
for (int p = max_len_start;
p <= max_len_end; p++)
Console.Write(arr[p] + " ");
}
// Driver code
public static void Main()
{
int []arr = { 4, 6, 8, 9, 8, 12,
14, 17, 15 };
int K = 2;
int N = arr.Length;
getMaxLengthSubarray(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript code for the above approach
// Function to return the maximum length
// sub-array such that the
// absolute difference between every two
// consecutive elements is K
function getMaxLengthSubarray(arr, N, K)
{
let l = N;
let i = 0, maxlen = 0;
let max_len_start, max_len_end;
while (i < l) {
let j = i;
while (i + 1 < l
&& (Math.abs(arr[i]
- arr[i + 1]) == K)) {
i++;
}
// Length of the valid sub-array
// currently under consideration
let currLen = i - j + 1;
// Update the maximum length subarray
if (maxlen < currLen) {
maxlen = currLen;
max_len_start = j;
max_len_end = i;
}
if (j == i)
i++;
}
// Print the maximum length subarray
for (let p = max_len_start;
p <= max_len_end; p++)
document.write(arr[p] + " ");
}
// Driver code
let arr = [4, 6, 8, 9, 8, 12,
14, 17, 15];
let K = 2;
let N = arr.length;
getMaxLengthSubarray(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción
4 6 8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)