Progresión aritmética más larga | DP-35

Dado un conjunto de números, encuentre la longitud de la progresión aritmética más larga ( LLAP ) en él.

Ejemplos:

set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}

set[] = {5, 10, 15, 20, 25, 30}
output = 6
The whole set is in AP

Para simplificar, hemos supuesto que el conjunto dado está ordenado. Siempre podemos agregar un paso de preprocesamiento para ordenar primero el conjunto y luego aplicar los siguientes algoritmos.

Una solución simple es considerar uno por uno cada par como los dos primeros elementos de AP y verificar los elementos restantes en un conjunto ordenado. Para considerar todos los pares como los primeros dos elementos, necesitamos ejecutar un bucle anidado O(n^2). Dentro de los bucles anidados, necesitamos un tercer bucle que busque linealmente más elementos en la progresión aritmética ( AP ). Este proceso toma O(n ³ ) tiempo.
Podemos resolver este problema en tiempo O(n ² ) usando Programación Dinámica . Para tener una idea de la solución DP, analicemos primero la solución del siguiente problema más simple.

Dado un conjunto ordenado, encuentre si existen tres elementos en Progresión aritmética o no

Tenga en cuenta que la respuesta es verdadera si hay 3 o más elementos en AP, de lo contrario, es falsa.
Para encontrar los tres elementos, primero fijamos un elemento como medio y buscamos otros dos (uno más pequeño y otro más grande). Comenzamos desde el segundo elemento y fijamos cada elemento como elemento intermedio. Para que un elemento set[j] sea medio de AP, deben existir los elementos ‘set[i]’ y ‘set[k]’ tales que set[i] + set[k] = 2*set[j] donde 0 <= yo < j y j < k <=n-1.
¿Cómo encontrar eficientemente i y k para un j dado?

Podemos encontrar i y k en tiempo lineal usando el siguiente algoritmo simple.

Inicializar i como j-1 y k como j+1

Haz lo siguiente mientras i >= 0 y k <= n-1

Si set[i] + set[k] es igual a 2*set[j], entonces hemos terminado.

Si set[i] + set[k] > 2*set[j], entonces decrementa i (do i–).

De lo contrario, si set[i] + set[k] < 2*set[j], entonces incremente k (do k++).

A continuación se muestra la implementación del algoritmo anterior para el problema más simple.

C++

// The function returns true if there exist three
// elements in AP Assumption: set[0..n-1] is sorted.
// The code strictly implements the algorithm provided
// in the reference.
bool arithmeticThree(vector<int> set, int n)
{
     
    // One by fix every element as middle element
    for(int j = 1; j < n - 1; j++)
    {
         
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2 * set[j])
                return true;
                 
            (set[i] + set[k] < 2 * set[j]) ? k++ : i--;
        }
    }
    return false;
}
 
// This code is contributed by Samim Hossain Mondal.

C

// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted.
// The code strictly implements the algorithm provided in the reference.
bool arithmeticThree(int set[], int n)
{
    // One by fix every element as middle element
    for (int j=1; j<n-1; j++)
    {
        // Initialize i and k for the current j
        int i = j-1, k = j+1;
 
        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            (set[i] + set[k] < 2*set[j])? k++ : i--;
        }
    }
 
    return false;
}

Java

// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted.
// The code strictly implements the algorithm provided in the reference.
static boolean arithmeticThree(int set[], int n)
{
    // One by fix every element as middle element
    for (int j = 1; j < n - 1; j++)
    {
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            (set[i] + set[k] < 2*set[j])? k++ : i--;
        }
    }
 
    return false;
}
 
// This code is contributed by gauravrajput1

Python3

# The function returns true if there exist three elements in AP
# Assumption: set[0..n-1] is sorted.
# The code strictly implements the algorithm provided in the reference.
def arithematicThree(set_,n):
 
    # One by fix every element as middle element
    for j in range(n):
         
        # Initialize i and k for the current j
        i,k=j-1,j+1
 
        # Find if there exist i and k that form AP
        # with j as middle element
        while i>-1 and k<n:
            if set_[i]+set_[k] == 2*set_[j]:
                return True
               
            elif set_[i]+set_[k]<2*set_[j]:
                i-=1
                 
            else:
                k+=1
    return False
  # This code is contributed by Kushagra Bansal

C#

// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted.
// The code strictly implements the algorithm provided in the reference.
static bool arithmeticThree(int []set, int n)
{
   
    // One by fix every element as middle element
    for (int j = 1; j < n - 1; j++)
    {
       
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            if(set[i] + set[k] < 2*set[j])
                k++;
            else
                i--;
        }
    }
 
    return false;
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// The function returns true if there exist three elements in AP
// Assumption: set[0..n-1] is sorted.
// The code strictly implements the algorithm provided in the reference.
function arithmeticThree(set, n){
    // One by fix every element as middle element
    for (let j=1; j<n-1; j++)
    {
        // Initialize i and k for the current j
        let i = j-1, k = j+1;
 
        // Find if there exist i and k that form AP
        // with j as middle element
        while (i >= 0 && k <= n-1)
        {
            if (set[i] + set[k] == 2*set[j])
                return true;
            (set[i] + set[k] < 2*set[j])? k++ : i--;
        }
    }
 
    return false;
}
</script>

¿Cómo extender la solución anterior para el problema original?

La función anterior devuelve un valor booleano. El resultado requerido del problema original es la longitud de la progresión aritmética más larga ( LLAP ) , que es un valor entero. Si el conjunto dado tiene dos o más elementos, entonces el valor de LLAP es al menos 2 (¿Por qué?).

La idea es crear una tabla 2D L[n][n]. Una entrada L[i][j] en esta tabla almacena LLAP con set[i] y set[j] como los dos primeros elementos de AP y j > i. La última columna de la tabla siempre es 2 (Por qué – ver el significado de L[i][j]). El resto de la tabla se llena de abajo a la derecha a arriba a la izquierda. Para llenar el resto de la tabla, primero se fija j (segundo elemento en AP). i y k se buscan para un j fijo. Si i y k se encuentran de tal manera que i, j, k forman un AP, entonces el valor de L[i][j] se establece como L[j][k] + 1. Tenga en cuenta que el valor de L[j] [k] debe haberse rellenado antes, ya que el ciclo atraviesa de las columnas de derecha a izquierda.

A continuación se muestra la implementación del algoritmo de Programación Dinámica.

C++

// C++ program to find Length of the Longest AP (llap) in a given sorted set.
// The code strictly implements the algorithm provided in the reference.
#include <iostream>
using namespace std;
 
// Returns length of the longest AP subset in a given set
int lenghtOfLongestAP(int set[], int n)
{
    if (n <= 2)  return n;
 
    // Create a table and initialize all values as 2. The value of
    // L[i][j] stores LLAP with set[i] and set[j] as first two
    // elements of AP. Only valid entries are the entries where j>i
    int L[n][n];
    int llap = 2;  // Initialize the result
 
    // Fill entries in last column as 2. There will always be
    // two elements in AP with last number of set as second
    // element in AP
    for (int i = 0; i < n; i++)
        L[i][n-1] = 2;
 
    // Consider every element as second element of AP
    for (int j=n-2; j>=1; j--)
    {
        // Search for i and k for j
        int i = j-1, k = j+1;
        while (i >= 0 && k <= n-1)
        {
           if (set[i] + set[k] < 2*set[j])
               k++;
 
           // Before changing i, set L[i][j] as 2
           else if (set[i] + set[k] > 2*set[j])
           {   L[i][j] = 2, i--;   }
 
           else
           {
               // Found i and k for j, LLAP with i and j as first two
               // elements is equal to LLAP with j and k as first two
               // elements plus 1. L[j][k] must have been filled
               // before as we run the loop from right side
               L[i][j] = L[j][k] + 1;
 
               // Update overall LLAP, if needed
               llap = max(llap, L[i][j]);
 
               // Change i and k to fill more L[i][j] values for
               // current j
               i--; k++;
           }
        }
 
        // If the loop was stopped due to k becoming more than
        // n-1, set the remaining entities in column j as 2
        while (i >= 0)
        {
            L[i][j] = 2;
            i--;
        }
    }
    return llap;
}
 
/* Driver program to test above function*/
int main()
{
    int set1[] = {1, 7, 10, 13, 14, 19};
    int n1 = sizeof(set1)/sizeof(set1[0]);
    cout <<   lenghtOfLongestAP(set1, n1) << endl;
 
    int set2[] = {1, 7, 10, 15, 27, 29};
    int n2 = sizeof(set2)/sizeof(set2[0]);
    cout <<   lenghtOfLongestAP(set2, n2) << endl;
 
    int set3[] = {2, 4, 6, 8, 10};
    int n3 = sizeof(set3)/sizeof(set3[0]);
    cout <<   lenghtOfLongestAP(set3, n3) << endl;
 
    return 0;
}

Java

// Java program to find Length of the
// Longest AP (llap) in a given sorted set.
// The code strictly implements the
// algorithm provided in the reference.
import java.io.*;
 
class GFG
{
    // Returns length of the longest
    // AP subset in a given set
    static int lenghtOfLongestAP(int set[], int n)
    {
        if (n <= 2) return n;
     
        // Create a table and initialize all
        // values as 2. The value ofL[i][j] stores
        // LLAP with set[i] and set[j] as first two
        // elements of AP. Only valid entries are
        // the entries where j>i
        int L[][] = new int[n][n];
         
         // Initialize the result
        int llap = 2;
     
        // Fill entries in last column as 2.
        // There will always be two elements in
        // AP with last number of set as second
        // element in AP
        for (int i = 0; i < n; i++)
            L[i][n - 1] = 2;
     
        // Consider every element as second element of AP
        for (int j = n - 2; j >= 1; j--)
        {
            // Search for i and k for j
            int i = j -1 , k = j + 1;
            while (i >= 0 && k <= n - 1)
            {
            if (set[i] + set[k] < 2 * set[j])
                k++;
     
            // Before changing i, set L[i][j] as 2
            else if (set[i] + set[k] > 2 * set[j])
            {
                L[i][j] = 2; i--;
                 
            }
     
            else
            {
                // Found i and k for j, LLAP with i and j as first two
                // elements is equal to LLAP with j and k as first two
                // elements plus 1. L[j][k] must have been filled
                // before as we run the loop from right side
                L[i][j] = L[j][k] + 1;
     
                // Update overall LLAP, if needed
                llap = Math.max(llap, L[i][j]);
     
                // Change i and k to fill
                // more L[i][j] values for current j
                i--; k++;
            }
            }
     
            // If the loop was stopped due
            // to k becoming more than
            // n-1, set the remaining
            // entities in column j as 2
            while (i >= 0)
            {
                L[i][j] = 2;
                i--;
            }
        }
        return llap;
    }
     
    // Driver program
    public static void main (String[] args)
    {
        int set1[] = {1, 7, 10, 13, 14, 19};
        int n1 = set1.length;
        System.out.println ( lenghtOfLongestAP(set1, n1));
     
        int set2[] = {1, 7, 10, 15, 27, 29};
        int n2 = set2.length;
        System.out.println(lenghtOfLongestAP(set2, n2));
     
        int set3[] = {2, 4, 6, 8, 10};
        int n3 = set3.length;
        System.out.println(lenghtOfLongestAP(set3, n3)) ;
     
     
    }
}
 
// This code is contributed by vt_m

Python3

# Python 3 program to find Length of the
# Longest AP (llap) in a given sorted set.
# The code strictly implements the algorithm
# provided in the reference
 
# Returns length of the longest AP
# subset in a given set
def lenghtOfLongestAP(set, n):
 
    if (n <= 2):
        return n
 
    # Create a table and initialize all
    # values as 2. The value of L[i][j]
    # stores LLAP with set[i] and set[j]
    # as first two elements of AP. Only
    # valid entries are the entries where j>i
    L = [[0 for x in range(n)]
            for y in range(n)]
    llap = 2 # Initialize the result
 
    # Fill entries in last column as 2.
    # There will always be two elements
    # in AP with last number of set as
    # second element in AP
    for i in range(n):
        L[i][n - 1] = 2
 
    # Consider every element as second
    # element of AP
    for j in range(n - 2, 0, -1):
 
        # Search for i and k for j
        i = j - 1
        k = j + 1
        while(i >= 0 and k <= n - 1):
 
            if (set[i] + set[k] < 2 * set[j]):
                k += 1
 
            # Before changing i, set L[i][j] as 2
            elif (set[i] + set[k] > 2 * set[j]):
                L[i][j] = 2
                i -= 1
 
            else:
 
                # Found i and k for j, LLAP with i and j
                # as first two elements are equal to LLAP
                # with j and k as first two elements plus 1.
                # L[j][k] must have been filled before as
                # we run the loop from right side
                L[i][j] = L[j][k] + 1
 
                # Update overall LLAP, if needed
                llap = max(llap, L[i][j])
 
                # Change i and k to fill more L[i][j]
                # values for current j
                i -= 1
                k += 1
 
                # If the loop was stopped due to k
                # becoming more than n-1, set the
                # remaining entities in column j as 2
                while (i >= 0):
                    L[i][j] = 2
                    i -= 1
    return llap
 
# Driver Code
if __name__ == "__main__":
     
    set1 = [1, 7, 10, 13, 14, 19]
    n1 = len(set1)
    print(lenghtOfLongestAP(set1, n1))
 
    set2 = [1, 7, 10, 15, 27, 29]
    n2 = len(set2)
    print(lenghtOfLongestAP(set2, n2))
 
    set3 = [2, 4, 6, 8, 10]
    n3 = len(set3)
    print(lenghtOfLongestAP(set3, n3))
 
# This code is contributed by ita_c

C#

// C# program to find Length of the
// Longest AP (llap) in a given sorted set.
// The code strictly implements the
// algorithm provided in the reference.
using System;
 
class GFG
{
// Returns length of the longest
// AP subset in a given set
static int lenghtOfLongestAP(int []set,
                             int n)
{
    if (n <= 2) return n;
 
    // Create a table and initialize
    // all values as 2. The value of
    // L[i][j] stores LLAP with set[i] 
    // and set[j] as first two elements
    // of AP. Only valid entries are
    // the entries where j>i
    int [,]L = new int[n, n];
     
    // Initialize the result
    int llap = 2;
 
    // Fill entries in last column as 2.
    // There will always be two elements
    // in AP with last number of set as
    // second element in AP
    for (int i = 0; i < n; i++)
        L[i, n - 1] = 2;
 
    // Consider every element as
    // second element of AP
    for (int j = n - 2; j >= 1; j--)
    {
        // Search for i and k for j
        int i = j - 1 , k = j + 1;
        while (i >= 0 && k <= n - 1)
        {
        if (set[i] + set[k] < 2 * set[j])
            k++;
 
        // Before changing i, set L[i][j] as 2
        else if (set[i] + set[k] > 2 * set[j])
        {
            L[i, j] = 2; i--;
             
        }
 
        else
        {
            // Found i and k for j, LLAP with
            // i and j as first two elements
            // is equal to LLAP with j and k
            // as first two elements plus 1.
            // L[j][k] must have been filled
            // before as we run the loop from
            // right side
            L[i, j] = L[j, k] + 1;
 
            // Update overall LLAP, if needed
            llap = Math.Max(llap, L[i, j]);
 
            // Change i and k to fill
            // more L[i][j] values for current j
            i--; k++;
        }
        }
 
        // If the loop was stopped due
        // to k becoming more than
        // n-1, set the remaining
        // entities in column j as 2
        while (i >= 0)
        {
            L[i, j] = 2;
            i--;
        }
    }
    return llap;
}
 
// Driver Code
static public void Main ()
{
    int []set1 = {1, 7, 10, 13, 14, 19};
    int n1 = set1.Length;
    Console.WriteLine(lenghtOfLongestAP(set1, n1));
 
    int []set2 = {1, 7, 10, 15, 27, 29};
    int n2 = set2.Length;
    Console.WriteLine(lenghtOfLongestAP(set2, n2));
 
    int []set3 = {2, 4, 6, 8, 10};
    int n3 = set3.Length;
    Console.WriteLine(lenghtOfLongestAP(set3, n3)) ;
}
}
 
// This code is contributed by Sach_Code

PHP

<?php
// PHP program to find Length of the
// Longest AP (llap) in a given sorted set.
 
// The code strictly implements the
// algorithm provided in the reference.
 
// Returns length of the longest AP
// subset in a given set
function lenghtOfLongestAP($set, $n)
{
    if ($n <= 2)
        return $n;
 
    // Create a table and initialize all
    // values as 2. The value of L[i][j]
    // stores LLAP with set[i] and set[j]
    // as first two elements of AP. Only
    // valid entries are the entries where j>i
    $L[$n][$n] = array(array());
    $llap = 2; // Initialize the result
 
    // Fill entries in last column as 2.
    // There will always be two elements
    // in AP with last number of set as
    // second element in AP
    for ($i = 0; $i < $n; $i++)
        $L[$i][$n - 1] = 2;
 
    // Consider every element as
    // second element of AP
    for ($j = $n - 2; $j >= 1; $j--)
    {
        // Search for i and k for j
        $i = $j - 1;
        $k = $j + 1;
        while ($i >= 0 && $k <= $n - 1)
        {
        if ($set[$i] + $set[$k] < 2 * $set[$j])
            $k++;
 
        // Before changing i, set L[i][j] as 2
        else if ($set[$i] + $set[$k] > 2 * $set[$j])
        {
            $L[$i][$j] = 2;
            $i--; }
 
        else
        {
            // Found i and k for j, LLAP with
            // i and j as first two elements
            // is equal to LLAP with j and k
            // as first two elements plus 1.
            // L[j][k] must have been filled
            // before as we run the loop from
            // right side
            $L[$i][$j] = $L[$j][$k] + 1;
 
            // Update overall LLAP, if needed
            $llap = max($llap, $L[$i][$j]);
 
            // Change i and k to fill more
            // L[i][j] values for current j
            $i--;
            $k++;
        }
        }
 
        // If the loop was stopped due to k
        // becoming more than n-1, set the
        // remaining entities in column j as 2
        while ($i >= 0)
        {
            $L[$i][$j] = 2;
            $i--;
        }
    }
    return $llap;
}
 
// Driver Code
$set1 = array(1, 7, 10, 13, 14, 19);
$n1 = sizeof($set1);
echo lenghtOfLongestAP($set1, $n1),"\n";
 
$set2 = array(1, 7, 10, 15, 27, 29);
$n2 = sizeof($set2);
echo lenghtOfLongestAP($set2, $n2),"\n";
 
$set3 = array(2, 4, 6, 8, 10);
$n3 = sizeof($set3);
echo lenghtOfLongestAP($set3, $n3),"\n";
 
// This code is contributed by Sach_Code
?>

Javascript

<script>
// Javascript program to find Length of the
// Longest AP (llap) in a given sorted set.
// The code strictly implements the
// algorithm provided in the reference.
     
    // Returns length of the longest
    // AP subset in a given set
    function lenghtOfLongestAP(set,n)
    {
        if (n <= 2)
            return n;
         
        // Create a table and initialize all
        // values as 2. The value ofL[i][j] stores
        // LLAP with set[i] and set[j] as first two
        // elements of AP. Only valid entries are
        // the entries where j>i
        let L=new Array(n);
        for(let i=0;i<n;i++)
        {
            L[i]=new Array(n);
        }
         
        // Initialize the result
        let llap = 2;
         
        // Fill entries in last column as 2.
        // There will always be two elements in
        // AP with last number of set as second
        // element in AP
        for (let i = 0; i < n; i++)
        {
            L[i][n - 1] = 2;
        }
        // Consider every element as second element of AP
        for (let j = n - 2; j >= 1; j--)
        {
            // Search for i and k for j
            let i = j -1 , k = j + 1;
            while (i >= 0 && k <= n - 1)
            {
                if (set[i] + set[k] < 2 * set[j])
                    k++;
          
                // Before changing i, set L[i][j] as 2
                else if (set[i] + set[k] > 2 * set[j])
                {
                    L[i][j] = 2; i--;
                      
                }
          
                else
                {
                    // Found i and k for j, LLAP with i and j as first two
                    // elements is equal to LLAP with j and k as first two
                    // elements plus 1. L[j][k] must have been filled
                    // before as we run the loop from right side
                    L[i][j] = L[j][k] + 1;
          
                    // Update overall LLAP, if needed
                    llap = Math.max(llap, L[i][j]);
          
                    // Change i and k to fill
                    // more L[i][j] values for current j
                    i--; k++;
                }
            }
            // If the loop was stopped due
            // to k becoming more than
            // n-1, set the remaining
            // entities in column j as 2
            while (i >= 0)
            {
                L[i][j] = 2;
                i--;
            }
        }
        return llap;
    }
     
    // Driver program
    let set1=[1, 7, 10, 13, 14, 19];
    let n1 = set1.length;
    document.write( lenghtOfLongestAP(set1, n1)+"<br>");
     
    let set2=[1, 7, 10, 15, 27, 29];
    let n2 = set2.length;
    document.write( lenghtOfLongestAP(set2, n2)+"<br>");
     
    let set3=[2, 4, 6, 8, 10];
    let n3 = set3.length;
    document.write( lenghtOfLongestAP(set3, n3)+"<br>");
     
     
    // This code is contributed by avanitrachhadiya2155
     
</script>

Producción

4
3
5

Complejidad de Tiempo: O(n ² )
Espacio Auxiliar: O(n ² )

¿Cómo reducir la complejidad del espacio para la solución anterior?
También podemos reducir la complejidad del espacio a O(n) .
A continuación se muestra la implementación del algoritmo de Programación Dinámica con Complejidad Espacial O(n) .

C++

// C++ program to find Length of the
// Longest AP (llap) in a given sorted set.
#include <bits/stdc++.h>
 
using namespace std;
 
// Returns length of the longest
// AP subset in a given set
int Solution(vector<int> A)
{
    int ans = 2;
    int n = A.size();
    if (n <= 2)
        return n;
 
    vector<int> llap(n, 2);
 
    sort(A.begin(), A.end());
 
    for (int j = n - 2; j >= 0; j--)
    {
        int i = j - 1;
        int k = j + 1;
        while (i >= 0 && k < n)
        {
            if (A[i] + A[k] == 2 * A[j])
            {
                llap[j] = max(llap[k] + 1, llap[j]);
                ans = max(ans, llap[j]);
                i -= 1;
                k += 1;
            }
            else if (A[i] + A[k] < 2 * A[j])
                k += 1;
            else
                i -= 1;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
    vector<int> a({ 9, 4, 7, 2, 10 });
    cout << Solution(a) << endl;
    return 0;
}
 
// This code is contributed by ashutosh450

Java

// Java program to find Length of the
// Longest AP (llap) in a given sorted set.
import java.util.*;
 
class GFG
{
 
// Returns length of the longest
// AP subset in a given set
static int Solution(int []A)
{
    int ans = 2;
    int n = A.length;
    if (n <= 2)
        return n;
 
    int []llap = new int[n];
    for(int i = 0; i < n; i++)
        llap[i] = 2;
 
    Arrays.sort(A);
 
    for (int j = n - 2; j >= 0; j--)
    {
        int i = j - 1;
        int k = j + 1;
        while (i >= 0 && k < n)
        {
            if (A[i] + A[k] == 2 * A[j])
            {
                llap[j] = Math.max(llap[k] + 1, llap[j]);
                ans = Math.max(ans, llap[j]);
                i -= 1;
                k += 1;
            }
            else if (A[i] + A[k] < 2 * A[j])
                k += 1;
            else
                i -= 1;
        }
    }
    return ans;
}
 
// Driver Code
public static void main(String[] args)
{
    int []a = { 9, 4, 7, 2, 10 };
    System.out.print(Solution(a) +"\n");
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python program to find Length 
# of the Longest AP (llap) in a given sorted set.
   
 # Returns length of the longest AP subset in a given set
   
class Solution:
    def Solve(self, A):
        ans = 2       
        n= len(A)
        if n<=2 :
            return n
        llap = [2]*n
        A.sort()
   
        for j in range(n-2, -1, -1):
            i= j-1
            k= j+1
            while(i>=0 and k<n):
                if A[i]+A[k] == 2*A[j]:
                    llap[j] = max(llap[k]+1,llap[j])
                    ans = max(ans, llap[j])
                    i-=1
                    k+=1
                elif A[i]+A[k] < 2*A[j]:
                    k += 1
                else:
                    i -= 1
   
        return ans 
   
# Driver program to test above function
obj = Solution()
a= [9, 4, 7, 2, 10]
print(obj.Solve(a))

C#

// C# program to find Length of the
// longest AP (llap) in a given sorted set.
using System;
 
class GFG
{
 
// Returns length of the longest
// AP subset in a given set
static int Solution(int []A)
{
    int ans = 2;
    int n = A.Length;
    if (n <= 2)
        return n;
 
    int []llap = new int[n];
    for(int i = 0; i < n; i++)
        llap[i] = 2;
 
    Array.Sort(A);
 
    for (int j = n - 2; j >= 0; j--)
    {
        int i = j - 1;
        int k = j + 1;
        while (i >= 0 && k < n)
        {
            if (A[i] + A[k] == 2 * A[j])
            {
                llap[j] = Math.Max(llap[k] + 1, llap[j]);
                ans = Math.Max(ans, llap[j]);
                i -= 1;
                k += 1;
            }
            else if (A[i] + A[k] < 2 * A[j])
                k += 1;
            else
                i -= 1;
        }
    }
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = { 9, 4, 7, 2, 10 };
    Console.Write(Solution(a) +"\n");
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// Javascript program to find Length of the
// Longest AP (llap) in a given sorted set.   
 
    // Returns length of the longest
    // AP subset in a given set
    function Solution(A)
    {
        let ans = 2;
        let n = A.length;
 
        if (n <= 2)
        {
            return n;
        }
         
        let llap = new Array(n);
        for(let i = 0; i < n; i++)
        {
            llap[i] = 2;
        }
        A.sort(function(a, b){return a-b});
        for (let j = n - 2; j >= 0; j--)
        {
            let i = j - 1;
            let k = j + 1;
            while (i >= 0 && k < n)
            {
                if (A[i] + A[k] == (2 * A[j]))
                {
                    llap[j] = Math.max((llap[k] + 1), llap[j]);
                    ans = Math.max(ans, llap[j]);
                    i -= 1;
                    k += 1;
                }
                else if (A[i] + A[k] < 2 * A[j])
                    k += 1;
                else
                    i -= 1;
            }
        }
        return ans;
    }
    // Driver Code
     
    let a=[9, 4, 7, 2, 10 ];
    document.write(Solution(a) +"<br>");
     
     
    // This code is contributed by rag2127
     
</script>

Producción

Complejidad de Tiempo: O(n ² )
Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta