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++14
// 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
// 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.
Python3
# 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#
// 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.
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por prophet1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA