Dada una array de n enteros positivos. La tarea es contar el número de subsecuencias de progresión aritmética en la array. Nota: La secuencia vacía o la secuencia de un solo elemento es una progresión aritmética. 1 <= arr[i] <= 1000000.
Ejemplos:
Input : arr[] = { 1, 2, 3 }
Output : 8
Arithmetic Progression subsequence from the
given array are: {}, { 1 }, { 2 }, { 3 }, { 1, 2 },
{ 2, 3 }, { 1, 3 }, { 1, 2, 3 }.
Input : arr[] = { 10, 20, 30, 45 }
Output : 12
Input : arr[] = { 1, 2, 3, 4, 5 }
Output : 23
Dado que la secuencia vacía y la secuencia de un solo elemento también son una progresión aritmética, inicializamos la respuesta con n (número de elementos en la array) + 1.
Ahora, necesitamos encontrar la subsecuencia de progresión aritmética de longitud mayor o igual a 2. Sea mínimo y máximo de la array sean minarr y maxarr respectivamente. Observa, en todas las subsecuencias de progresión aritmética, el rango de diferencia común será de (minarr – maxarr) a (maxarr – minarr). Ahora, para cada diferencia común, digamos d, calcule la subsecuencia de longitud mayor o igual a 2 usando programación dinámica.
Sea dp[i] el número de subsecuencias que terminan en arr[i] y tienen como diferencia común d. Asi que,
El número de subsecuencias de longitud mayor o igual a 2 con diferencia común d es la suma de dp[i] – 1, 0 <= i = 2 con diferencia d. Para acelerar, almacene la suma de dp[j] con arr[j] + d = arr[i] y j < i.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ program to find number of AP
// subsequences in the given array
#include<bits/stdc++.h>
#define MAX 1000001
using namespace std;
int numofAP(int a[], int n)
{
// initializing the minimum value and
// maximum value of the array.
int minarr = INT_MAX, maxarr = INT_MIN;
// Finding the minimum and maximum
// value of the array.
for (int i = 0; i < n; i++)
{
minarr = min(minarr, a[i]);
maxarr = max(maxarr, a[i]);
}
// dp[i] is going to store count of APs ending
// with arr[i].
// sum[j] is going to store sun of all dp[]'s
// with j as an AP element.
int dp[n], sum[MAX];
// Initialize answer with n + 1 as single elements
// and empty array are also DP.
int ans = n + 1;
// Traversing with all common difference.
for (int d=(minarr-maxarr); d<=(maxarr-minarr); d++)
{
memset(sum, 0, sizeof sum);
// Traversing all the element of the array.
for (int i = 0; i < n; i++)
{
// Initialize dp[i] = 1.
dp[i] = 1;
// Adding counts of APs with given differences
// and a[i] is last element.
// We consider all APs where an array element
// is previous element of AP with a particular
// difference
if (a[i] - d >= 1 && a[i] - d <= 1000000)
dp[i] += sum[a[i] - d];
ans += dp[i] - 1;
sum[a[i]] += dp[i];
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << numofAP(arr, n) << endl;
return 0;
}
Java
// Java program to find number of AP
// subsequences in the given array
import java.util.Arrays;
class GFG {
static final int MAX = 1000001;
static int numofAP(int a[], int n)
{
// initializing the minimum value and
// maximum value of the array.
int minarr = +2147483647;
int maxarr = -2147483648;
// Finding the minimum and maximum
// value of the array.
for (int i = 0; i < n; i++) {
minarr = Math.min(minarr, a[i]);
maxarr = Math.max(maxarr, a[i]);
}
// dp[i] is going to store count of
// APs ending with arr[i].
// sum[j] is going to store sun of
// all dp[]'s with j as an AP element.
int dp[] = new int[n];
int sum[] = new int[MAX];
// Initialize answer with n + 1 as
// single elements and empty array
// are also DP.
int ans = n + 1;
// Traversing with all common
// difference.
for (int d = (minarr - maxarr);
d <= (maxarr - minarr); d++)
{
Arrays.fill(sum, 0);
// Traversing all the element
// of the array.
for (int i = 0; i < n; i++) {
// Initialize dp[i] = 1.
dp[i] = 1;
// Adding counts of APs with
// given differences and a[i]
// is last element.
// We consider all APs where
// an array element is previous
// element of AP with a particular
// difference
if (a[i] - d >= 1 &&
a[i] - d <= 1000000)
dp[i] += sum[a[i] - d];
ans += dp[i] - 1;
sum[a[i]] += dp[i];
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int n = arr.length;
System.out.println(numofAP(arr, n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find number of AP # subsequences in the given array MAX = 1000001 def numofAP(a, n): # initializing the minimum value and # maximum value of the array. minarr = +2147483647 maxarr = -2147483648 # Finding the minimum and # maximum value of the array. for i in range(n): minarr = min(minarr, a[i]) maxarr = max(maxarr, a[i]) # dp[i] is going to store count of APs ending # with arr[i]. # sum[j] is going to store sun of all dp[]'s # with j as an AP element. dp = [0 for i in range(n + 1)] # Initialize answer with n + 1 as single # elements and empty array are also DP. ans = n + 1 # Traversing with all common difference. for d in range((minarr - maxarr), (maxarr - minarr) + 1): sum = [0 for i in range(MAX + 1)] # Traversing all the element of the array. for i in range(n): # Initialize dp[i] = 1. dp[i] = 1 # Adding counts of APs with given differences # and a[i] is last element. # We consider all APs where an array element # is previous element of AP with a particular # difference if (a[i] - d >= 1 and a[i] - d <= 1000000): dp[i] += sum[a[i] - d] ans += dp[i] - 1 sum[a[i]] += dp[i] return ans # Driver code arr = [ 1, 2, 3 ] n = len(arr) print(numofAP(arr, n)) # This code is contributed by Anant Agarwal.
C#
// C# program to find number of AP
// subsequences in the given array
using System;
class GFG {
static int MAX = 1000001;
// Function to find number of AP
// subsequences in the given array
static int numofAP(int []a, int n)
{
// initializing the minimum value and
// maximum value of the array.
int minarr = +2147483647;
int maxarr = -2147483648;
int i;
// Finding the minimum and maximum
// value of the array.
for (i = 0; i < n; i++)
{
minarr = Math.Min(minarr, a[i]);
maxarr = Math.Max(maxarr, a[i]);
}
// dp[i] is going to store count of
// APs ending with arr[i].
// sum[j] is going to store sun of
// all dp[]'s with j as an AP element.
int []dp = new int[n];
int []sum = new int[MAX];
// Initialize answer with n + 1 as
// single elements and empty array
// are also DP.
int ans = n + 1;
// Traversing with all common
// difference.
for (int d = (minarr - maxarr);
d <= (maxarr - minarr); d++)
{
for(i = 0; i < MAX; i++)
sum[i]= 0;
// Traversing all the element
// of the array.
for ( i = 0; i < n; i++)
{
// Initialize dp[i] = 1.
dp[i] = 1;
// Adding counts of APs with
// given differences and a[i]
// is last element.
// We consider all APs where
// an array element is previous
// element of AP with a particular
// difference
if (a[i] - d >= 1 &&
a[i] - d <= 1000000)
dp[i] += sum[a[i] - d];
ans += dp[i] - 1;
sum[a[i]] += dp[i];
}
}
return ans;
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 3};
int n = arr.Length;
Console.WriteLine(numofAP(arr, n));
}
}
// This code is contributed by vt_m.
Javascript
<script>
// Javascript program to find number of AP
// subsequences in the given array
let MAX = 1000001;
function numofAP(a, n)
{
// initializing the minimum value and
// maximum value of the array.
let minarr = +2147483647;
let maxarr = -2147483648;
// Finding the minimum and maximum
// value of the array.
for (let i = 0; i < n; i++) {
minarr = Math.min(minarr, a[i]);
maxarr = Math.max(maxarr, a[i]);
}
// dp[i] is going to store count of
// APs ending with arr[i].
// sum[j] is going to store sun of
// all dp[]'s with j as an AP element.
let dp = new Array(n);
let sum = new Array(MAX);
// Initialize answer with n + 1 as
// single elements and empty array
// are also DP.
let ans = n + 1;
// Traversing with all common
// difference.
for (let d = (minarr - maxarr);
d <= (maxarr - minarr); d++)
{
sum.fill(0);
// Traversing all the element
// of the array.
for (let i = 0; i < n; i++) {
// Initialize dp[i] = 1.
dp[i] = 1;
// Adding counts of APs with
// given differences and a[i]
// is last element.
// We consider all APs where
// an array element is previous
// element of AP with a particular
// difference
if (a[i] - d >= 1 &&
a[i] - d <= 1000000)
dp[i] += sum[a[i] - d];
ans += dp[i] - 1;
sum[a[i]] += dp[i];
}
}
return ans;
}
let arr = [ 1, 2, 3 ];
let n = arr.length;
document.write(numofAP(arr, n));
</script>
Producción :
8
Este artículo es una contribución de Anuj Chauhan . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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