Suma máxima de subarreglo de longitud principal

Dada una array arr[] de tamaño N , la tarea es encontrar la suma máxima de subarreglo que se puede obtener de modo que la longitud del subarreglo sea primo.

Ejemplos:

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

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

Enfoque ingenuo:  la idea es la siguiente:

Genere todos los subarreglos posibles y, a partir de ellos, encuentre los de longitud prima. 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 calcularse previamente mediante el algoritmo Sieve 
• Ahora, para cada longitud prima, calcule la suma y tome el máximo de ella    

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement sieve of eratosthenes
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;
            }
        }
    }
}
 
// Function to find the sum
// of prime length subarrays
int primeLenSum(int a[], int N)
{
    vector<bool> prime(N + 1, true);
    sieve(N, prime);
    int ans = INT_MIN;
 
    // Traversing to find max sum
    // of prime subarray
    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;
}
 
// Driver code
int main()
{
    int arr[] = { 2, -1, 3, -2, 1, -1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << primeLenSum(arr, N) << "\n";
    return 0;
}

4

Complejidad temporal: O(N ³ )
Espacio auxiliar: O(N) 

Enfoque eficiente: para resolver el problema, siga la siguiente idea:

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 (ya que 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 array:
  • 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
• Ahora, 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++ code for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to implement sieve of eratosthenes
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;
            }
        }
    }
}
 
// Function to find the maximum subarray sum
// having prime length
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;
 
    // Finding prime length subarray
    // with maximum sum
    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;
}
 
// Driver code
int main()
{
    int arr[] = { 2, -1, 3, -2, 1, -1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    cout << primeLenSum(arr, N);
    return 0;
}

// Java code for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
 
    // Function to implement sieve of eratosthenes
    static boolean[] sieve(int n, boolean[] 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;
                }
            }
        }
        return prime;
    }
 
    // Function to find the maximum subarray sum having
    // prime length
    static int primeLenSum(int[] a, int N)
    {
        boolean[] prime = new boolean[N + 1];
        Arrays.fill(prime, true);
        prime = sieve(N, prime);
        int max_ending_here = 0;
        int max_for_primes = 0, sz = 0;
 
        // Finding prime length subarray with maximum sum
        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;
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 2, -1, 3, -2, 1, -1 };
        int N = arr.length;
 
        // Function call
        System.out.print(primeLenSum(arr, N));
    }
}
 
// This code is contributed by lokeshmvs21.

4

Complejidad de tiempo: O(N * log(logN))
Espacio auxiliar: O(N)