Suma máxima de subarreglo de longitud principal

/ c++ / Por

Dada una matriz Arr[] de tamaño nortela tarea es encontrar la suma máxima de subarreglo que se puede obtener para que la longitud del subarreglo sea primo.

Ejemplos:

Aporte: Arr[] = {2, -1, 3, -2, 1, -1}
Salida: 4
El subarreglo {2, -1, 3} de tamaño = 3 (número primo)

aporte: Arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Salida: 7
El subarreglo {4, -1, -2, 1, 5} de magnitud = 5 (número primo)

Enfoque ingenuo: La idea es la siguiente:

Genere todos los subarreglos posibles y encuentre el que tiene longitud prima de ellos. Encuentre la suma máxima entre ellos.

Siga los pasos dados para resolver el problema:

  • Genere todos los subarreglos posibles de todas las longitudes utilizando bucles for anidados.
  • Encuentre la suma de cada subarreglo de longitud prima.
  • Los números que son primos pueden ser precalculados por el algoritmo Sieve
  • Ahora calcule la suma para cada longitud prima y tome su máximo

A continuación se muestra la implementación del enfoque anterior:

C++

 

#include <bits/stdc++.h>

using namespace std;

 

void sieve(int N, vector<bool>& prime)

{

    prime[1] = false;

    prime[0] = false;

    for (int i = 2; i * i <= N; i++) {

        if (prime[i]) {

            for (int p = i * i; p <= N; p += i) {

                prime[p] = false;

            }

        }

    }

}

 

int primeLenSum(int a[], int N)

{

    vector<bool> prime(N + 1, true);

    sieve(N, prime);

    int ans = INT_MIN;

 

    

    

    for (int i = 0; i < N; i++) {

        for (int j = i + 1; j < N; j++) {

            if (prime[j - i]) {

                int sum = 0;

                for (int k = i; k <= j; k++)

                    sum += a[k];

                ans = max(ans, sum);

            }

        }

    }

 

    return ans;

}

 

int main()

{

    int arr[] = { 2, -1, 3, -2, 1, -1 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    

    cout << primeLenSum(arr, N) << "n";

    return 0;

}

Complejidad del tiempo: A3)
cuarto auxiliar: A)

Enfoque eficiente: Siga la siguiente idea para resolver el problema:

Use el algoritmo de Kadane y actualice la respuesta solo si la longitud del subarreglo es primo.

Siga los pasos dados para resolver el problema:

  • Inicialice max_so_far = INT_MIN (porque la suma puede ser negativa) y max_ending_here = 0 (para realizar un seguimiento de la suma actual)
  • Bucle para iterar cada elemento de la matriz:
    • max_ending_here es igual a max_ending_here + arr[i]
    • Si max_so_far es menor que max_ending_here, actualice max_so_far
    • Si max_ending_here es menor que 0, establezca max_ending_here = 0
    • Devolver max_so_far
  • Para calcular la suma del subarreglo de la longitud principal, debemos realizar un seguimiento del tamaño del subarreglo y verificar si el tamaño es primo o no.

A continuación se muestra la implementación de la idea anterior:

C++14

 

#include <bits/stdc++.h>

using namespace std;

 

void sieve(int n, vector<bool>& prime)

{

    prime[1] = false;

    prime[0] = false;

    for (int i = 2; i * i <= n; i++) {

        if (prime[i]) {

            for (int p = i * i; p <= n; p += i) {

                prime[p] = false;

            }

        }

    }

}

 

int primeLenSum(int a[], int N)

{

    vector<bool> prime(N + 1, true);

    sieve(N, prime);

    int max_ending_here = 0;

    int max_for_primes = 0, sz = 0;

 

    

    

    for (int i = 0; i < N; i++) {

        max_ending_here += a[i];

        sz = sz + 1;

        if (max_ending_here < 0) {

            max_ending_here = 0;

            sz = 0;

        }

 

        if (max_ending_here > max_for_primes && prime[sz])

            max_for_primes = max_ending_here;

    }

    return max_for_primes;

}

 

int main()

{

    int arr[] = { 2, -1, 3, -2, 1, -1 };

    int N = sizeof(arr) / sizeof(arr[0]);

 

    

    cout << primeLenSum(arr, N);

    return 0;

}

Complejidad del tiempo: O(N * registro(registroN))
cuarto auxiliar: A)

Su Calificación Nos Ayuda a Mejorar