El subarreglo más largo que forma una progresión aritmética (AP) con una diferencia común dada

Dado un arreglo arr[] de N enteros y un entero K , la tarea es encontrar la longitud del subarreglo más largo que forma una progresión aritmética que tiene una diferencia común K .

Ejemplos:

Entrada: arr[] = {3, 4, 5}, K = 1
Salida: 3
Explicación: El subarreglo más largo que forma un AP con diferencia común 1 es {3, 4, 5}.

Entrada: arr[] = {10, 7, 4, 6, 8, 10, 11}, K = 2
Salida: 4
Explicación: El subarreglo más largo posible que forma un AP con diferencia común como 2 es {4, 6, 8, 10} .

Enfoque: El problema dado es un problema basado en la implementación que se puede resolver utilizando la técnica de la ventana deslizante . Siga los pasos que se mencionan a continuación para resolver el problema:

• Recorra la array dada y mantenga una variable que almacene el número de variables en la ventana actual.
• Si la diferencia entre el elemento actual y el elemento anterior en la array es K , incremente el tamaño de la ventana actual; de lo contrario, restablezca el tamaño de la ventana a 1 .
• Imprime la diferencia máxima como respuesta.

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find longest subarray
// forming an Arithmetic Progression
// with the given common difference
int maxlenAP(int arr[], int& n, int& d)
{
    // Stores the length of
    // the current window
    int count = 1;
 
    // Stores final answer
    int maxLen = INT_MIN;
 
    // Loop to traverse array
    for (int i = 1; i < n; i++) {
        if (arr[i] - arr[i - 1] == d)
 
            // Increment window size
            count++;
        else
 
            // Reset window size
            count = 1;
 
        // Update answer
        maxLen = max(maxLen, count);
    }
 
    // Return Answer
    return maxLen;
}
 
// Driver Code
int main()
{
    int arr[] = { 10, 7, 4, 6, 8, 10, 11 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 2;
 
    cout << maxlenAP(arr, N, K);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG {
     
// Function to find longest subarray
// forming an Arithmetic Progression
// with the given common difference
static int maxlenAP(int []arr, int n, int d)
{
   
    // Stores the length of
    // the current window
    int count = 1;
 
    // Stores final answer
    int maxLen = Integer.MIN_VALUE;
 
    // Loop to traverse array
    for (int i = 1; i < n; i++) {
        if (arr[i] - arr[i - 1] == d)
 
            // Increment window size
            count++;
        else
 
            // Reset window size
            count = 1;
 
        // Update answer
        maxLen = Math.max(maxLen, count);
    }
 
    // Return Answer
    return maxLen;
}
 
// Driver Code
public static void main(String args[])
{
    int []arr = { 10, 7, 4, 6, 8, 10, 11 };
    int N = arr.length;
    int K = 2;
 
    System.out.println(maxlenAP(arr, N, K));
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python code for the above approach
 
# Function to find longest subarray
# forming an Arithmetic Progression
# with the given common difference
def maxlenAP(arr, n, d):
 
    # Stores the length of
    # the current window
    count = 1
 
    # Stores final answer
    maxLen = 10 ** -9
 
    # Loop to traverse array
    for i in range(1, n):
        if (arr[i] - arr[i - 1] == d):
            # Increment window size
            count += 1
        else:
            # Reset window size
            count = 1
 
        # Update answer
        maxLen = max(maxLen, count)
 
    # Return Answer
    return maxLen
 
 
# Driver Code
arr = [10, 7, 4, 6, 8, 10, 11]
N = len(arr)
K = 2
print(maxlenAP(arr, N, K))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG {
     
// Function to find longest subarray
// forming an Arithmetic Progression
// with the given common difference
static int maxlenAP(int []arr, int n, int d)
{
   
    // Stores the length of
    // the current window
    int count = 1;
 
    // Stores final answer
    int maxLen = Int32.MinValue;
 
    // Loop to traverse array
    for (int i = 1; i < n; i++) {
        if (arr[i] - arr[i - 1] == d)
 
            // Increment window size
            count++;
        else
 
            // Reset window size
            count = 1;
 
        // Update answer
        maxLen = Math.Max(maxLen, count);
    }
 
    // Return Answer
    return maxLen;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 10, 7, 4, 6, 8, 10, 11 };
    int N = arr.Length;
    int K = 2;
 
    Console.Write(maxlenAP(arr, N, K));
 
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find longest subarray
      // forming an Arithmetic Progression
      // with the given common difference
      function maxlenAP(arr, n, d)
      {
       
          // Stores the length of
          // the current window
          let count = 1;
 
          // Stores final answer
          let maxLen = Number.MIN_VALUE;
 
          // Loop to traverse array
          for (let i = 1; i < n; i++)
          {
              if (arr[i] - arr[i - 1] == d)
 
                  // Increment window size
                  count++;
              else
 
                  // Reset window size
                  count = 1;
 
              // Update answer
              maxLen = Math.max(maxLen, count);
          }
 
          // Return Answer
          return maxLen;
      }
 
      // Driver Code
      let arr = [10, 7, 4, 6, 8, 10, 11];
      let N = arr.length;
      let K = 2;
 
      document.write(maxlenAP(arr, N, K));
 
// This code is contributed by Potta Lokesh
  </script>

4

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