Dado un arreglo arr[] de tamaño N , la tarea es encontrar la longitud del subarreglo más largo que forma una progresión aritmética .
Ejemplos:
Entrada: arr[] = {3, 4, 5}
Salida: 3
Explicación: El subarreglo más largo que forma un AP es {3, 4, 5} con diferencia común 1.
Entrada: {10, 7, 4, 6, 8, 10, 11}
Salida: 4
Explicación: El subarreglo más largo posible que forma un AP es {4, 6, 8, 10} con diferencia común (= 2).
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todos los subarreglos posibles y, para cada subarreglo, verificar si la diferencia entre los elementos adyacentes permanece igual o no. Entre todos los subarreglos que satisfacen la condición, almacene la longitud del subarreglo más largo e imprímalo como resultado.
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea aquí es observar que siempre que la diferencia entre el par actual de elementos adyacentes no sea igual a la diferencia entre el par anterior de elementos adyacentes, compare la longitud del subarreglo anterior con el máximo obtenido hasta ahora y comience un nuevo subarreglo y repita en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable res para almacenar la longitud del subarreglo más largo que forma un AP .
- Iterar sobre las arrays restantes y comparar la diferencia adyacente actual con la diferencia adyacente anterior.
- Itere sobre la array y, para cada elemento, calcule la diferencia entre el par actual de elementos adyacentes y verifique si es igual al par anterior de elementos adyacentes. Si se determina que es cierto, continúe con el subarreglo en curso incrementando res en 1.
- De lo contrario, considere un nuevo subarreglo. Actualice la longitud máxima obtenida hasta el momento, es decir, res comparándola con la longitud del subarreglo anterior.
- Finalmente, devuelve res como la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the length
// of longest subarray forming an AP
int getMaxLength(int arr[], int N)
{
//single number is also an AP
//with common difference as 0
if(N==1)
return 1;
// Minimum possible length of
// required subarray is 2
int res = 2;
// Stores the length of the
// current subarray
int dist = 2;
// Stores the common difference
// of the current AP
int curradj = (arr[1] - arr[0]);
// Stores the common difference
// of the previous AP
int prevadj = (arr[1] - arr[0]);
for (int i = 2; i < N; i++) {
curradj = arr[i] - arr[i - 1];
// If the common differences
// are found to be equal
if (curradj == prevadj) {
// Continue the previous subarray
dist++;
}
// Start a new subarray
else {
prevadj = curradj;
// Update the length to
// store maximum length
res = max(res, dist);
dist = 2;
}
}
// Update the length to
// store maximum length
res = max(res, dist);
// Return the length of
// the longest subarray
return res;
}
// Driver Code
int main()
{
int arr[] = {10, 7, 4, 6, 8, 10, 11};
int N = sizeof(arr) / sizeof(arr[0]);
cout << getMaxLength(arr, N);
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Function to return the length
// of longest subarray forming an AP
static int getMaxLength(int arr[], int N)
{
// Minimum possible length of
// required subarray is 2
int res = 2;
// Stores the length of the
// current subarray
int dist = 2;
// Stores the common difference
// of the current AP
int curradj = (arr[1] - arr[0]);
// Stores the common difference
// of the previous AP
int prevadj = (arr[1] - arr[0]);
for (int i = 2; i < N; i++)
{
curradj = arr[i] - arr[i - 1];
// If the common differences
// are found to be equal
if (curradj == prevadj)
{
// Continue the previous subarray
dist++;
}
// Start a new subarray
else
{
prevadj = curradj;
// Update the length to
// store maximum length
res = Math.max(res, dist);
dist = 2;
}
}
// Update the length to
// store maximum length
res = Math.max(res, dist);
// Return the length of
// the longest subarray
return res;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = {10, 7, 4,
6, 8, 10, 11};
int N = arr.length;
System.out.print(getMaxLength(arr, N));
}
}
// This code is contributed by shikhasingrajput
Python3
# python3 Program to implement # the above approach # Function to return the length # of longest subarray forming an AP def getMaxLength(arr, N): # Minimum possible length of # required subarray is 2 res = 2 # Stores the length of the # current subarray dist = 2 # Stores the common difference # of the current AP curradj = (arr[1] - arr[0]) # Stores the common difference # of the previous AP prevadj = (arr[1] - arr[0]) for i in range(2, N): curradj = arr[i] - arr[i - 1] # If the common differences # are found to be equal if (curradj == prevadj): # Continue the previous subarray dist += 1 # Start a new subarray else: prevadj = curradj # Update the length to # store maximum length res = max(res, dist) dist = 2 # Update the length to # store maximum length res = max(res, dist) # Return the length of # the longest subarray return res # Driver Code if __name__ == "__main__": arr = [10, 7, 4, 6, 8, 10, 11] N = len(arr) print(getMaxLength(arr, N)) # This code is contributed by Chitranayal
C#
// C# Program to implement
// the above approach
using System;
public class GFG{
// Function to return the length
// of longest subarray forming an AP
static int getMaxLength(int []arr,
int N)
{
// Minimum possible length of
// required subarray is 2
int res = 2;
// Stores the length of the
// current subarray
int dist = 2;
// Stores the common difference
// of the current AP
int curradj = (arr[1] - arr[0]);
// Stores the common difference
// of the previous AP
int prevadj = (arr[1] - arr[0]);
for (int i = 2; i < N; i++)
{
curradj = arr[i] - arr[i - 1];
// If the common differences
// are found to be equal
if (curradj == prevadj)
{
// Continue the previous subarray
dist++;
}
// Start a new subarray
else
{
prevadj = curradj;
// Update the length to
// store maximum length
res = Math.Max(res, dist);
dist = 2;
}
}
// Update the length to
// store maximum length
res = Math.Max(res, dist);
// Return the length of
// the longest subarray
return res;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = {10, 7, 4,
6, 8, 10, 11};
int N = arr.Length;
Console.Write(getMaxLength(arr, N));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript Program to implement
// the above approach
// Function to return the length
// of longest subarray forming an AP
function getMaxLength(arr, N)
{
// Minimum possible length of
// required subarray is 2
let res = 2;
// Stores the length of the
// current subarray
let dist = 2;
// Stores the common difference
// of the current AP
let curradj = (arr[1] - arr[0]);
// Stores the common difference
// of the previous AP
let prevadj = (arr[1] - arr[0]);
for (let i = 2; i < N; i++) {
curradj = arr[i] - arr[i - 1];
// If the common differences
// are found to be equal
if (curradj == prevadj) {
// Continue the previous subarray
dist++;
}
// Start a new subarray
else {
prevadj = curradj;
// Update the length to
// store maximum length
res = Math.max(res, dist);
dist = 2;
}
}
// Update the length to
// store maximum length
res = Math.max(res, dist);
// Return the length of
// the longest subarray
return res;
}
// Driver Code
let arr= [ 10, 7, 4, 6, 8, 10, 11 ];
let N = arr.length;
document.write(getMaxLength(arr, N));
// This code is contributed by Mayank Tyagi
</script>
Producción:
4
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deepakkumar144 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA