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++
|
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
|
Complejidad del tiempo: O(N * registro(registroN))
cuarto auxiliar: A)