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