Dada una array arr[] que consta de N enteros, la tarea es encontrar la longitud de la subsecuencia más larga que forma una progresión aritmética .
Ejemplos:
Entrada: arr[] = {5, 10, 15, 20, 25, 30}
Salida: 6
Explicación:
Todo el conjunto está en AP teniendo una diferencia común = 5.
Por lo tanto, la longitud es 4.Entrada: arr[] = { 20, 1, 15, 3, 10, 5, 8 }
Salida: 4
Explicación:
La subsecuencia más larga que tiene la misma diferencia es { 20, 15, 10, 5 }.
La subsecuencia anterior tiene la misma diferencia para todos los pares consecutivos, es decir, (15 – 20) = (10 – 15) = (5 – 10) = -5.
Por lo tanto, la longitud es 4.
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las subsecuencias posibles de la array dada e imprimir la longitud de la subsecuencia más larga que tenga la misma diferencia entre pares de elementos adyacentes. Tiempo
Complejidad: O(N*2 N )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . A continuación se muestran los pasos:
- Inicialice una array auxiliar dp[][] donde dp[i][j] indica la longitud de la subsecuencia que comienza en i y tiene una diferencia común como j .
- Iterar sobre la array usando bucles anidados i desde N – 1 hasta 0 y j desde i+1 hasta N .
- Suponga que arr[i] y arr[j] son los dos primeros elementos de la sucesión y sea d su diferencia .
- Ahora bien, se presentan dos casos:
- dp[j][d] = 0 : No existe tal secuencia que comience con arr[j] y tenga su diferencia como d . En este caso dp[i][d] = 2 , ya que solo podemos tener arr[i] y arr[j] en la secuencia.
- dp[j][d] > 0 : Existe una secuencia que comienza con arr[j] y tiene diferencia entre elementos adyacentes como d . En este caso, la relación es dp[i][d] = 1 + dp[j] [re] .
- Finalmente, imprima la longitud máxima de todas las subsecuencias formadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that finds the longest
// arithmetic subsequence having the
// same absolute difference
int lenghtOfLongestAP(int A[], int n)
{
// Stores the length of sequences
// having same difference
unordered_map<int,
unordered_map<int, int> >
dp;
// Stores the resultant length
int res = 2;
// Iterate over the array
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int d = A[j] - A[i];
// Update length of subsequence
dp[d][j] = dp[d].count(i)
? dp[d][i] + 1
: 2;
res = max(res, dp[d][j]);
}
}
// Return res
return res;
}
// Driver Code
int main()
{
// Given array arr[]
int arr[] = { 20, 1, 15, 3, 10, 5, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << lenghtOfLongestAP(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function that finds the longest
// arithmetic subsequence having the
// same absolute difference
static int lenghtOfLongestAP(int A[], int n)
{
// Stores the length of sequences
// having same difference
Map<Integer,
Map<Integer,
Integer>> dp = new HashMap<Integer,
Map<Integer,
Integer>>();
// Stores the resultant length
int res = 2;
// Iterate over the array
for(int i = 0; i < n; ++i)
{
for(int j = i + 1; j < n; ++j)
{
int d = A[j] - A[i];
Map<Integer, Integer> temp;
// Update length of subsequence
if (dp.containsKey(d))
{
temp = dp.get(d);
if (temp.containsKey(i))
temp.put(j, temp.get(i) + 1);
else
temp.put(j, 2);
}
else
{
temp = new HashMap<Integer, Integer>();
temp.put(j, 2);
}
dp.put(d, temp);
res = Math.max(res, temp.get(j));
}
}
// Return res
return res;
}
// Driver Code
public static void main(String[] args)
{
// Given array arr[]
int arr[] = { 20, 1, 15, 3, 10, 5, 8 };
int N = arr.length;
// Function Call
System.out.println(lenghtOfLongestAP(arr, N));
}
}
// This code is contributed by jithin
Python3
# Python3 program for the above approach
# Function that finds the longest
# arithmetic subsequence having the
# same absolute difference
def lenghtOfLongestAP(A, n) :
# Stores the length of sequences
# having same difference
dp = {}
# Stores the resultant length
res = 2
# Iterate over the array
for i in range(n) :
for j in range(i + 1, n) :
d = A[j] - A[i]
# Update length of subsequence
if d in dp :
if i in dp[d] :
dp[d][j] = dp[d][i] + 1
else :
dp[d][j] = 2
else :
dp[d] = {}
dp[d][j] = 2
if d in dp :
if j in dp[d] :
res = max(res, dp[d][j])
# Return res
return res
# Given array arr[]
arr = [ 20, 1, 15, 3, 10, 5, 8 ]
N = len(arr)
# Function Call
print(lenghtOfLongestAP(arr, N))
# This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that finds the longest
// arithmetic subsequence having the
// same absolute difference
static int lenghtOfLongestAP(int []A, int n)
{
// Stores the length of sequences
// having same difference
Dictionary<int,
Dictionary<int, int>> dp = new Dictionary<int,
Dictionary<int, int>>();
// Stores the resultant length
int res = 2;
// Iterate over the array
for(int i = 0; i < n; ++i)
{
for(int j = i + 1; j < n; ++j)
{
int d = A[j] - A[i];
// Update length of subsequence
if (dp.ContainsKey(d))
{
if (dp[d].ContainsKey(i))
{
dp[d][j] = dp[d][i] + 1;
}
else
{
dp[d][j] = 2;
}
}
else
{
dp[d] = new Dictionary<int, int>();
dp[d][j] = 2;
}
res = Math.Max(res, dp[d][j]);
}
}
// Return res
return res;
}
// Driver Code
public static void Main(string[] args)
{
// Given array arr[]
int []arr = { 20, 1, 15, 3, 10, 5, 8 };
int N = arr.Length;
// Function call
Console.Write(lenghtOfLongestAP(arr, N));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript program for the above approach
// Function that finds the longest
// arithmetic subsequence having the
// same absolute difference
function lenghtOfLongestAP(A, n)
{
// Stores the length of sequences
// having same difference
var dp = new Map();
// Stores the resultant length
var res = 2;
// Iterate over the array
for (var i = 0; i < n; ++i) {
for (var j = i + 1; j < n; ++j) {
var d = A[j] - A[i];
// Update length of subsequence
if (dp.has(d))
{
if (dp.get(d).has(i))
{
var tmp = dp.get(d);
tmp.set(j, dp.get(d).get(i)+1);
}
else
{
var tmp = new Map();
tmp.set(j, 2);
dp.set(d, tmp);
}
}
else
{
var tmp = new Map();
tmp.set(j, 2);
dp.set(d, tmp);
}
res = Math.max(res, dp.get(d).get(j));
}
}
// Return res
return res;
}
// Driver Code
// Given array arr[]
var arr = [20, 1, 15, 3, 10, 5, 8];
var N = arr.length;
// Function Call
document.write( lenghtOfLongestAP(arr, N));
</script>
Producción:
4
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por vatsalanarang y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA