Progresión aritmética más larga que se puede formar con la diferencia común dada d

Dada una array desordenada a[] de tamaño n y un entero d que es la diferencia común, la tarea es encontrar la longitud del AP más largo que se puede formar para todos los j, mayor que algún i(<n), 

if a[j] = a[i] + (j-i) * d

es decir, a[j] está en el AP de a[i] del índice i al j.
Ejemplos: 
 

Entrada: n = 6, d = 2 
arr[] = {1, 2, 5, 7, 9, 85} 
Salida: 4 
El AP más largo, teniendo en cuenta los índices, es [1, 5, 7, 9] 
desde 5 está 2 índices por delante de 1 y encajaría en el AP si se comenzara 
desde el índice 0. como 5 = 1 + (2 – 0) * 2. Entonces, la salida es 4.
Entrada: n = 10, d = 3 
arr[] = {1, 4, 2, 5, 20, 11, 56, 100, 20, 23} 
Salida: 5 
El AP más largo, teniendo en cuenta los índices, es [2, 5, 11, 20, 23] 
ya que 11 son 2 índices por delante de 5 y 20 está 3 índices por delante de 11. Por lo tanto 
, encajarían en el AP si comenzaran desde el índice 2. 
 

Enfoque ingenuo: para cada elemento, calcule la longitud del AP más largo que podría formar e imprima el máximo entre ellos. Implica una complejidad temporal O(n ² ) .
Un enfoque eficiente es usar Hashing.
Cree un mapa donde la clave es el elemento inicial de un AP y su valor es la cantidad de elementos en ese AP. La idea es actualizar el valor en la clave ‘a’ (que está en el índice i y cuyo elemento inicial aún no está en el mapa) por 1 siempre que el elemento en el índice j(>i) pueda estar en el AP de ‘a ‘(como elemento inicial). Luego imprimimos el valor máximo entre todos los valores en el mapa.
 

// C++ code for finding the
// maximum length of AP
 
#include <bits/stdc++.h>
using namespace std;
int maxlenAP(int* a, int n, int d)
{
    // key=starting element of an AP,
    // value=length of AP
    unordered_map<int, int> m;
 
    // since the length of longest AP is at least
    // one i.e. the number itself.
    int maxt = 1;
 
    // if element a[i]'s starting element(i.e., a[i]-i*d)
    // is not in map then its value is 1 else there already
    // exists a starting element of an AP of which a[i]
    // can be a part.
    for (int i = 0; i < n; i++) {
        m[a[i] - i * d]++;
    }
 
    // auto operator stores the key,
    // value pair type from the map.
    for (auto& it : m)
        if (it.second > maxt)
 
            // calculating the length of longest AP.
            maxt = it.second;
 
    return maxt;
}
 
// Driver code
int main()
{
    int n = 10, d = 3;
    int a[10] = { 1, 4, 2, 5, 20, 11, 56, 100, 20, 23 };
 
    cout << maxlenAP(a, n, d) << endl;
 
    return 0;
}

// Java code for finding the
// maximum length of AP
import java.io.*;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Map;
import java.lang.*;
 
class GFG
{
static int maxlenAP(int a[],
                    int n, int d)
{
    // key=starting element of an AP,
    // value=length of AP
    HashMap<Integer, Integer> m =
                    new HashMap<Integer, Integer>();
 
    // since the length of longest
    // AP is at least one i.e.
    // the number itself.
    int maxt = 1;
 
    // if element a[i]'s starting
    // element(i.e., a[i]-i*d)
    // is not in map then its value
    // is 1 else there already
    // exists a starting element of
    // an AP of which a[i] can be
    // a part.
    for (int i = 0; i < n; i++)
    {
        if(m.containsKey(a[i] - i * d))
        {
            int freq = m.get(a[i] - i * d);
            freq++;
            m.put(a[i] - i * d, freq);
        }
        else
        {
            m.put(a[i] - i * d, 1);
        }
    }
 
    // auto operator stores the key,
    // value pair type from the map.
    for(Entry<Integer, Integer> val: m.entrySet())
    {
        if (maxt < val.getValue())
            maxt = val.getValue();
    }
    return maxt;
}
 
// Driver code
public static void main(String[] args)
{
    int n = 10, d = 3;
    int a[] = new int[]{ 1, 4, 2, 5, 20, 11,
                         56, 100, 20, 23 };
 
    System.out.print(maxlenAP(a, n, d) + "\n");
}
}

// C# code for finding the
// maximum length of AP
using System;
using System.Collections.Generic;
 
class GFG
{
    static int maxlenAP(int []a,
                    int n, int d)
    {
        // key=starting element of an AP,
        // value=length of AP
        Dictionary<int,int> m =
                    new Dictionary<int,int>();
 
        // since the length of longest
        // AP is at least one i.e.
        // the number itself.
        int maxt = 1;
 
        // if element a[i]'s starting
        // element(i.e., a[i]-i*d)
        // is not in map then its value
        // is 1 else there already
        // exists a starting element of
        // an AP of which a[i] can be
        // a part.
        for (int i = 0; i < n; i++)
        {
            if(m.ContainsKey(a[i] - i * d))
            {
                int freq = m[a[i] - i * d];
                freq++;
                m.Remove(a[i] - i * d);
                m.Add(a[i] - i * d, freq);
            }
            else
            {
                m.Add(a[i] - i * d, 1);
            }
        }
 
        // auto operator stores the key,
        // value pair type from the map.
        foreach(var val in m)
        {
            if (maxt < val.Value)
                maxt = val.Value;
        }
        return maxt;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 10, d = 3;
    int []a = new int[]{ 1, 4, 2, 5, 20, 11,
                        56, 100, 20, 23 };
 
    Console.Write(maxlenAP(a, n, d) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python code for finding the
# maximum length of AP
 
def maxlenAP(a, n, d):
 
    # key = starting element of an AP,
    # value = length of AP
    m = dict()
 
    # since the length of longest AP is at least
    # one i.e. the number itself.
    maxt = 1
 
    # if element a[i]'s starting element(i.e., a[i]-i*d)
    # is not in map then its value is 1 else there already
    # exists a starting element of an AP of which a[i]
    # can be a part.
    for i in range(n):
        if (a[i] - i * d) in m:
            m[a[i] - i * d] += 1
        else:
            m[a[i] - i * d] = 1
 
    # In this it variable will be
    # storing key value of dictionary.
    for it in m:
        if m[it] > maxt:
 
            # calculating the length of longest AP.
            maxt = m[it]
 
    return maxt
 
 
# Driver code
if __name__ == "__main__":
    n, d = 10, 3
    a = [1, 4, 2, 5, 20, 11, 56, 100, 20, 23]
    print(maxlenAP(a, n, d))
 
# This code is contributed by
# sanjeev2552

<script>
 
// JavaScript code for finding the
// maximum length of AP
 
function maxlenAP(a, n, d) {
    // key=starting element of an AP,
    // value=length of AP
    let m = new Map();
 
    // since the length of longest AP is at least
    // one i.e. the number itself.
    let maxt = 1;
 
    // if element a[i]'s starting element(i.e., a[i]-i*d)
    // is not in map then its value is 1 else there already
    // exists a starting element of an AP of which a[i]
    // can be a part.
    for (let i = 0; i < n; i++) {
        if (m.has(a[i] - i * d)) {
            m.set(a[i] - i * d, m.get(a[i] - i * d) + 1)
        } else {
            m.set(a[i] - i * d, 1)
        }
    }
 
    // auto operator stores the key,
    // value pair type from the map.
    for (let it of m)
        if (it[1] > maxt)
 
            // calculating the length of longest AP.
            maxt = it[1];
 
    return maxt;
}
 
// Driver code
 
let n = 10, d = 3;
let a = [1, 4, 2, 5, 20, 11, 56, 100, 20, 23];
 
document.write(maxlenAP(a, n, d) + "<br>");
 
</script>

5

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)