Recuento de subsecuencias AP (progresión aritmética) en una array

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *