Given an array arr[] of size N, the task is to find the maximum subarray sum that can be obtained such that the length of the subarray should be prime.
Examples :
Input: arr[] = {2, -1, 3, -2, 1, -1}
Output: 4
The subarray {2, -1, 3} of size = 3 (prime number)input: arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}
Output: 7
The subarray {4, -1, -2, 1, 5} of size = 5 (prime number)
Naive Approach: The idea is as follows:
Generate all possible subarrays and from them find the ones with prime length. Find the maximum sum among them.
Follow the given steps to solve the problem:
- Generate all possible subarrays of all lengths using nested for-loops.
- Find the sum of each prime length subarray.
- The numbers which are primes can be precomputed by Sieve algorithm
- Now for each prime length, calculate the sum and take the maximum of it
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to implement sieve of eratosthenesvoid 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 subarraysint 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 codeint 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;} |
Java
// Java program for the above approachimport java.io.*;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 sum of prime length subarrays static int primeLenSum(int[] a, int N) { boolean[] prime = new boolean[N + 1]; for (int i = 0; i < N; i++) { prime[i] = true; } prime = sieve(N, prime); int ans = Integer.MIN_VALUE; // 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 = Math.max(ans, sum); } } } return ans; } 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. |
Python3
import sysdef sieve(N, prime): prime[1] = False prime[0] = False for i in range(2,N+1): if i*i<=N: if (prime[i]): for p in range(i*i,N+1): prime[p] = False p+=i def primeLenSum(a,N): prime=[True for i in range(N+1)] sieve(N, prime) ans = -sys.maxsize - 1 for i in range(N): for j in range(i+1,N): if (prime[j - i]): sum = 0 for k in range(i,j+1): sum += a[k] ans = max(ans, sum); return ansif __name__ == '__main__': arr = [ 2, -1, 3, -2, 1, -1 ] N=len(arr) # Function call print( primeLenSum(arr, N)) # This code is contributed by vikkycirus. |
C#
// C# program for the above approachusing System;public class GFG { // Function to implement sieve of eratosthenes static bool[] sieve(int N, 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; } } } return prime; } // Function to find the sum of prime length subarrays static int primeLenSum(int[] a, int N) { bool[] prime = new bool[N + 1]; for (int i = 0; i < N; i++) { prime[i] = true; } prime = sieve(N, prime); int ans = Int32.MinValue; // 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 = Math.Max(ans, sum); } } } return ans; } static public void Main() { // Code int[] arr = { 2, -1, 3, -2, 1, -1 }; int N = arr.Length; // Function call Console.Write(primeLenSum(arr, N)); }}// This code is contributed by lokeshmvs21. |
Javascript
// Javascript program for the above approach// Function to implement sieve of eratosthenesfunction sieve(N, prime) { prime[1] = false; prime[0] = false; for (let i = 2; i * i <= N; i++) { if (prime[i]) { for (let p = i * i; p <= N; p += i) { prime[p] = false; } } }}// Function to find the sum// of prime length subarraysfunction primeLenSum(a, N) { let prime = new Array(N + 1).fill(true); sieve(N, prime); let ans = Number.MIN_SAFE_INTEGER; // Traversing to find max sum // of prime subarray for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { if (prime[j - i]) { let sum = 0; for (let k = i; k <= j; k++) sum += a[k]; ans = Math.max(ans, sum); } } } return ans;}// Driver codelet arr = [2, -1, 3, -2, 1, -1];let N = arr.length;// Function callconsole.log(primeLenSum(arr, N));// This code is contributed by akashish__ |
Output
4
Time complexity: O(N3)
Auxiliary Space: O(N)
Efficient Approach: To solve the problem follow the below idea:
Use Kadane’s algorithm, and update the answer only if the length of the subarray is prime.
Follow the given steps to solve the problem:
- Initialize max_so_far = INT_MIN (since sum can be negative), and max_ending_here = 0 (to keep track of the current sum )
- Loop to iterate each element of the array:
- max_ending_here is equal to max_ending_here + arr[i]
- If max_so_far is less than max_ending_here then update max_so_far
- If max_ending_here is less than 0 then set max_ending_here = 0
- Return max_so_far
- Now for calculating the subarray sum of prime length we have to keep track of the subarray size and have to check whether the size is prime or not
Below is the implementation of the above idea :
C++14
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to implement sieve of eratosthenesvoid 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 lengthint 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 codeint 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
// Java code for the above approachimport 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. |
Python3
# Function to implement sieve of eratosthenesdef sieve(n, prime): prime[1] = False prime[0] = False for i in range(2, int(n**(1/2))+1): if prime[i]: for p in range(i*i, n+1, i): prime[p] = False# Function to find the maximum subarray sum# having prime lengthdef primeLenSum(a, N): prime = [True] * (N + 1) sieve(N, prime) max_ending_here = 0 max_for_primes = 0 sz = 0 # Finding prime length subarray # with maximum sum for i in range(N): 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 and prime[sz]: max_for_primes = max_ending_here return max_for_primes# Driver codearr = [2, -1, 3, -2, 1, -1]N = len(arr)# Function callprint(primeLenSum(arr, N))# This code is contributed by akashish__ |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;public class Gfg { // Function to implement sieve of eratosthenes static void sieve(int n, int[] prime) { prime[1] = 0; prime[0] = 0; for (int i = 2; i * i <= n; i++) { if (prime[i]==1) { for (int p = i * i; p <= n; p += i) { prime[p] = 0; } } } } // Function to find the maximum subarray sum // having prime length static int primeLenSum(int []a, int N) { int[] prime = new int[N+1]; for(int i=0; i<N+1; i++) prime[i]=1; 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]==1) max_for_primes = max_ending_here; } return max_for_primes; } // Driver code public static void Main(string[] args) { int[] arr = { 2, -1, 3, -2, 1, -1 }; int N = arr.Length; // Function call Console.WriteLine(primeLenSum(arr, N)); }} |
Javascript
// Function to implement sieve of eratosthenesfunction sieve(n, prime) { prime[1] = false; prime[0] = false; for (let i = 2; i * i <= n; i++) { if (prime[i]) { for (let p = i * i; p <= n; p += i) { prime[p] = false; } } }}// Function to find the maximum subarray sum// having prime lengthfunction primeLenSum(a, N) { const prime = Array(N + 1).fill(true); sieve(N, prime); let max_ending_here = 0; let max_for_primes = 0, sz = 0; // Finding prime length subarray // with maximum sum for (let 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 codeconst arr = [2, -1, 3, -2, 1, -1];const N = arr.length;// Function callconsole.log(primeLenSum(arr, N));// This code is contributed by akashish__ |
Output
4
Time Complexity: O(N * log(logN))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
