Longitud del subarreglo más largo tal que la diferencia entre elementos adyacentes es K

Dada una array arr[] de tamaño N y entero K . La tarea es encontrar la longitud del 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: 2
Explicación: Solo un subarreglo que tiene diferencia entre adyacentes como 1 es {12, 13}.

Entrada: arr[] = {4, 6, 8, 9, 8, 12, 14, 17, 15}, K = 2 Salida: 3
Explicación :
Hay tres subarreglos {4, 6, 8}, {12, 14} y {17, 15}.
{4, 6, 8} tiene la mayor longitud.

Entrada: arr[] = {2, 2, 4, 6}, K = 1
Salida: 1
Explicación: Ningún subarreglo de longitud mayor que satisface este criterio.

Enfoque: a partir del primer elemento de la array, busque la primera sub-array válida y almacene su longitud y luego, a partir del siguiente elemento (el primer elemento que no se incluyó en la primera sub-array), busque otra sub-array válida. formación. Repita el proceso hasta que se hayan encontrado todos los subconjuntos válidos y luego imprima la longitud del subconjunto más largo.

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the maximum length
// of the sub-array such that the
// absolute difference between every two
// consecutive elements is K
int getMaxLength(int arr[], int N, int K)
{
    int l = N;
    int i = 0, maxlen = 0;
    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
        if (maxlen < currLen)
            maxlen = currLen;
 
        if (j == i)
            i++;
    }
 
    // Return the maximum possible length
    return maxlen;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 2, 4, 6 };
    int K = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << getMaxLength(arr, N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
 
// Function to return the maximum length
// of the sub-array such that the
// absolute difference between every two
// consecutive elements is K
static int getMaxLength(int arr[], int N, int K)
{
    int l = N;
    int i = 0, maxlen = 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
        if (maxlen < currLen)
            maxlen = currLen;
 
        if (j == i)
            i++;
    }
 
    // Return the maximum possible length
    return maxlen;
}
 
// Driver code
public static void main(String args[])
{
    int arr[] = { 2, 2, 4, 6 };
    int K = 1;
    int N =  arr.length; 
    System.out.print(getMaxLength(arr, N, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python implementation of the approach
 
# Function to return the maximum length
# of the sub-array such that the
# absolute difference between every two
# consecutive elements is K
def getMaxLength (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
        if (maxlen < currLen):
            maxlen = currLen;
 
        if (j == i):
            i += 1
 
    # Return the maximum possible length
    return maxlen;
 
# Driver code
arr = [2, 2, 4, 6];
K = 1;
N = len(arr)
print(getMaxLength(arr, N, K));
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG
{
 
  // Function to return the maximum length
  // of the sub-array such that the
  // absolute difference between every two
  // consecutive elements is K
  static int getMaxLength(int []arr, int N, int K)
  {
    int l = N;
    int i = 0, maxlen = 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
      if (maxlen < currLen)
        maxlen = currLen;
 
      if (j == i)
        i++;
    }
 
    // Return the maximum possible length
    return maxlen;
  }
 
  // Driver Code
  public static void Main()
  {
    int []arr = { 2, 2, 4, 6 };
    int K = 1;
    int N =  arr.Length;
    Console.Write(getMaxLength(arr, N, K));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
    // JavaScript implementation of the approach
 
    // Function to return the maximum length
    // of the sub-array such that the
    // absolute difference between every two
    // consecutive elements is K
    const getMaxLength = (arr, N, K) => {
        let l = N;
        let i = 0, maxlen = 0;
        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
            if (maxlen < currLen)
                maxlen = currLen;
 
            if (j == i)
                i++;
        }
 
        // Return the maximum possible length
        return maxlen;
    }
 
    // Driver code
    let arr = [2, 2, 4, 6];
    let K = 1;
    let N = arr.length;
    document.write(getMaxLength(arr, N, K));
 
// This code is contributed by rakeshsahni
 
</script>

1

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)