Given an array arr[] of integers of size n, find the maximum sum of a continuous subarray such that the subarray only contains prime integers. In other words, no non-prime integer should appear within the chosen subarray.
Examples:
Input: arr[] = [1, 7, 4, 2, 3, 8, 5, 11, 13], n = 9
Output: 29
Explanation: The subarray [5, 11, 13] is the only subarray with prime integers and with a maximum sum of 29.Input: arr = [1, 4, 6, 7, 10], n = 5
Output: 7
Explanation: The maximum sum of a continuous subarray such that the subarray only contains prime integers is {7} with sum 7.
Naive Approach: The basic way to solve the problem is as follows:
The idea involves checking all possible subarrays that only contain prime integers and keeping track of the maximum sum.
Steps that were to follow the above approach:
- Initialize maxSum to 0
- Loop through all subarrays of arr
- Check if the current subarray only contains prime integers
- If it does, calculate its sum
- If its sum is greater than maxSum, update maxSum
- Check if the current subarray only contains prime integers
- Return maxSum
Below is the code to implement the above steps:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // function to check if a number is prime bool isPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) return false ; } return true ; } // Function to find the maximum sum // of a continuous subarray that // contains only prime integers int maxPrimeSubarraySum( int arr[], int n) { int maxSum = 0; for ( int i = 0; i < n; i++) { int currentSum = 0; for ( int j = i; j < n; j++) { if (isPrime(arr[j])) { // If integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = max(maxSum, currentSum); } else { // If integer is not prime, // break and move to // next subarray break ; } } } return maxSum; } // Driver's code int main() { int arr[] = { 1, 3, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); // Call maxPrimeSubarraySum function to // find the maximum sum of a continuous // subarray with prime integers int sum = maxPrimeSubarraySum(arr, n); cout << "Maximum sum of prime subarray is: " << sum << endl; return 0; } |
Java
import java.util.*; public class Main { // function to check if a number is prime public static boolean isPrime( int n) { if (n <= 1 ) return false ; for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) return false ; } return true ; } // function to find the maximum sum of a continuous // subarray that contains only prime integers public static int maxPrimeSubarraySum( int [] arr, int n) { int maxSum = 0 ; for ( int i = 0 ; i < n; i++) { int currentSum = 0 ; for ( int j = i; j < n; j++) { if (isPrime( arr[j])) { // if integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = Math.max(maxSum, currentSum); } else { // if integer is not prime, break and // move to next subarray break ; } } } return maxSum; } // Driver's code public static void main(String[] args) { int [] arr = { 1 , 3 , 5 , 6 , 7 }; int n = arr.length; // call maxPrimeSubarraySum function to find the // maximum sum of a continuous subarray with prime // integers int sum = maxPrimeSubarraySum(arr, n); System.out.println( "Maximum sum of prime subarray is: " + sum); } } |
Python3
import math # function to check if a number is prime def isPrime(n): if n < = 1 : return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : return False return True # function to find the maximum sum of a continuous subarray that contains only prime integers def maxPrimeSubarraySum(arr): n = len (arr) maxSum = 0 for i in range (n): currentSum = 0 for j in range (i, n): if isPrime(arr[j]): # if integer is prime, add it to the current sum and update max sum if necessary currentSum + = arr[j] maxSum = max (maxSum, currentSum) else : # if integer is not prime, break and move to next subarray break return maxSum arr = [ 1 , 3 , 5 , 6 , 7 ] # call maxPrimeSubarraySum function to find the maximum sum of a continuous subarray with prime integers sum = maxPrimeSubarraySum(arr) print ( "Maximum sum of prime subarray is:" , sum ) |
C#
// C# code to implement the above approach using System; class GFG { // Function to check if a number is prime static bool IsPrime( int n) { if (n <= 1) return false ; for ( int i = 2; i * i <= n; i++) { if (n % i == 0) return false ; } return true ; } // Function to find the maximum sum // of a continuous subarray that // contains only prime integers static int MaxPrimeSubarraySum( int [] arr, int n) { int maxSum = 0; for ( int i = 0; i < n; i++) { int currentSum = 0; for ( int j = i; j < n; j++) { if (IsPrime(arr[j])) { // If integer is prime, // add it to the current // sum and update max sum // if necessary currentSum += arr[j]; maxSum = Math.Max(maxSum, currentSum); } else { // If integer is not prime, // break and move to // next subarray break ; } } } return maxSum; } static void Main( string [] args) { int [] arr = { 1, 3, 5, 6, 7 }; int n = arr.Length; // Call MaxPrimeSubarraySum function to // find the maximum sum of a continuous // subarray with prime integers int sum = MaxPrimeSubarraySum(arr, n); Console.WriteLine( "Maximum sum of prime subarray is: " + sum); } } |
Javascript
// function to check if a number is prime function isPrime(n) { if (n <= 1) return false ; for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i == 0) return false ; } return true ; } // function to find the maximum sum of a continuous subarray that contains only prime integers function maxPrimeSubarraySum(arr) { let n = arr.length; let maxSum = 0; for (let i = 0; i < n; i++) { let currentSum = 0; for (let j = i; j < n; j++) { if (isPrime(arr[j])) { // if integer is prime, add it to the current sum and update max sum if necessary currentSum += arr[j]; maxSum = Math.max(maxSum, currentSum); } else { // if integer is not prime, break and move to next subarray break ; } } } return maxSum; } let arr = [1, 3, 5, 6, 7]; let sum = maxPrimeSubarraySum(arr); console.log( "Maximum sum of prime subarray is: " + sum); |
Maximum sum of prime subarray is: 8
Time Complexity: O(N^2*sqrt(N)), since we are checking all possible subarrays and then checking if each integer in the subarray is prime.
Auxiliary Space: O(1), since we are not using any additional data structures.
Efficient Approach: To solve the problem using Hashmap follow the below steps:
- Inside the maxPrimeSubarraySum function, we initialize the variables maxSum, currentSum, start, and end.
- We then loop through the input array arr, incrementing the end variable each time.
- If the current element of arr is prime, we add it to currentSum, update maxSum if currentSum is greater, and move the start pointer forward.
- If the current element of arr is not prime, we subtract the prime integers from currentSum until the current element is no longer included in the subarray.
- We repeat steps 5-6 until we have looped through the entire array.
- Finally, we return the maxSum.
Below is the code to implement the above steps:
C++
// C++ code for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a number is prime bool isPrime( int n) { if (n <= 1) // 1 is not prime return false ; for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) // If n is divisible by i, // it's not prime return false ; } return true ; } // Function to find the maximum sum of a // continuous subarray such that the // subarray only contains prime integers int maxPrimeSubarraySum( int arr[], int n) { unordered_map< int , int > freq; // Map to store frequency of elements int maxSum = 0, currentSum = 0; // Variables to store maximum sum // and current sum for ( int i = 0; i < n; i++) { if (isPrime(arr[i])) // If the element is prime { currentSum += arr[i]; // Add it to the current sum freq[arr[i]]++; // Increment its frequency in // the map while (freq[arr[i]] > 1) // If the element is not unique { // Remove the non-unique // elements from the // current sum and map freq[arr[i - freq[arr[i]] + 1]]--; currentSum -= arr[i - freq[arr[i]] + 1]; } maxSum = max(maxSum, currentSum); // Update maximum sum } else // If the element is not prime { freq.clear(); // Reset the frequency map currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique // prime integers } // Driver's code int main() { int arr[] = { 1, 3, 5, 6, 7 }; // Sample input array int n = sizeof (arr) / sizeof (arr[0]); // Size of the input array int sum = maxPrimeSubarraySum(arr, n); // Find the maximum sum of a subarray // with unique prime integers cout << "Maximum sum of prime subarray is: " << sum << endl; // Print the result return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { // Function to check if a number is prime public static boolean isPrime( int n) { if (n <= 1 ) // 1 is not prime return false ; for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) // If n is divisible by i, it's // not prime return false ; } return true ; } // Function to find the maximum sum of a continuous // subarray such that the subarray only contains prime // integers public static int maxPrimeSubarraySum( int [] arr, int n) { Map<Integer, Integer> freq = new HashMap<>(); // Map to store frequency of // elements int maxSum = 0 , currentSum = 0 ; // Variables to store maximum // sum and current sum for ( int i = 0 ; i < n; i++) { if (isPrime( arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum freq.put(arr[i], freq.getOrDefault(arr[i], 0 ) + 1 ); // Increment its // frequency in the map while ( freq.get(arr[i]) > 1 ) { // If the element is not unique // Remove the non-unique elements from // the current sum and map freq.put( arr[i - freq.get(arr[i]) + 1 ], freq.get( arr[i - freq.get(arr[i]) + 1 ]) - 1 ); currentSum -= arr[i - freq.get(arr[i]) + 1 ]; } maxSum = Math.max( maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.clear(); // Reset the frequency map currentSum = 0 ; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique prime // integers } // Driver's code public static void main(String[] args) { int [] arr = { 1 , 3 , 5 , 6 , 7 }; // Sample input array int n = arr.length; // Size of the input array int sum = maxPrimeSubarraySum( arr, n); // Find the maximum sum of a subarray // with unique prime integers System.out.println( "Maximum sum of prime subarray is: " + sum); // Print the result } } |
Python3
import math # Function to check if a number is prime def isPrime(n): if n < = 1 : # 1 is not prime return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : # If n is divisible by i, it's not prime return False return True # Function to find the maximum sum of a continuous subarray # such that the subarray only contains prime integers def maxPrimeSubarraySum(arr): freq = {} # Dictionary to store frequency of elements maxSum = 0 # Variable to store maximum sum currentSum = 0 # Variable to store current sum for i in range ( len (arr)): if isPrime(arr[i]): # If the element is prime currentSum + = arr[i] # Add it to the current sum if arr[i] in freq: freq[arr[i]] + = 1 # Increment its frequency in the dictionary else : freq[arr[i]] = 1 while freq[arr[i]] > 1 : # If the element is not unique # Remove the non-unique elements from the current sum and dictionary freq[arr[i - freq[arr[i]] + 1 ]] - = 1 currentSum - = arr[i - freq[arr[i]] + 1 ] maxSum = max (maxSum, currentSum) # Update maximum sum else : # If the element is not prime freq = {} # Reset the frequency dictionary currentSum = 0 # Reset the current sum return maxSum # Return the maximum sum of a subarray with unique prime integers arr = [ 1 , 3 , 5 , 6 , 7 ] # Sample input array # Find the maximum sum of a subarray with unique prime integers sum = maxPrimeSubarraySum(arr) print ( "Maximum sum of prime subarray is:" , sum ) # Print the result |
C#
using System; using System.Collections.Generic; class Program { // Function to check if a number is prime static bool IsPrime( int n) { if (n <= 1) // 1 is not prime return false ; for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If n is divisible by i, // it's not prime return false ; } } return true ; } // Function to find the maximum sum of a // continuous subarray such that the // subarray only contains prime integers static int MaxPrimeSubarraySum( int [] arr, int n) { Dictionary< int , int > freq = new Dictionary< int , int >(); // Dictionary to store frequency of elements int maxSum = 0, currentSum = 0; // Variables to store maximum sum // and current sum for ( int i = 0; i < n; i++) { if (IsPrime(arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum if (!freq.ContainsKey(arr[i])) { freq[arr[i]] = 0; } freq[arr[i]]++; // Increment its frequency in the dictionary while (freq[arr[i]] > 1) { // If the element is not unique // Remove the non-unique elements from the // current sum and dictionary freq[arr[i - freq[arr[i]] + 1]]--; currentSum -= arr[i - freq[arr[i]] + 1]; } maxSum = Math.Max(maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.Clear(); // Reset the frequency dictionary currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a // subarray with unique prime integers } // Driver's code static void Main( string [] args) { int [] arr = { 1, 3, 5, 6, 7 }; // Sample input array int n = arr.Length; // Size of the input array int sum = MaxPrimeSubarraySum(arr, n); // Find the maximum sum of a subarray // with unique prime integers Console.WriteLine( "Maximum sum of prime subarray is: " + sum); // Print the result } } // Contributed by Aditi Tyagi |
Javascript
// Function to check if a number is prime function isPrime(n) { if (n <= 1) { // 1 is not prime return false ; } for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { // If n is divisible by i, it's not prime return false ; } } return true ; } // Function to find the maximum sum of a continuous subarray // such that the subarray only contains prime integers function maxPrimeSubarraySum(arr) { const freq = new Map(); // Map to store frequency of elements let maxSum = 0, currentSum = 0; // Variables to store maximum sum and current sum for (let i = 0; i < arr.length; i++) { if (isPrime(arr[i])) { // If the element is prime currentSum += arr[i]; // Add it to the current sum freq.set(arr[i], (freq.get(arr[i]) || 0) + 1); // Increment its frequency in the map while (freq.get(arr[i]) > 1) { // If the element is not unique // Remove the non-unique elements from the current sum and map freq.set(arr[i - freq.get(arr[i]) + 1], freq.get(arr[i] - 1)); currentSum -= arr[i - freq.get(arr[i]) + 1]; } maxSum = Math.max(maxSum, currentSum); // Update maximum sum } else { // If the element is not prime freq.clear(); // Reset the frequency map currentSum = 0; // Reset the current sum } } return maxSum; // Return the maximum sum of a subarray with unique prime integers } const arr = [1, 3, 5, 6, 7]; // Sample input array const sum = maxPrimeSubarraySum(arr); // Find the maximum sum of a subarray with unique prime integers console.log( "Maximum sum of prime subarray is:" , sum); // Print the result |
Maximum sum of prime subarray is: 8
Time Complexity: O(N*sqrt(N)) because the function uses a single pass of the input array, and the operations performed in each iteration use sqrt(N) time in the prime function.
Auxiliary Space: O(N), because we used a hash map to store the indices of the unique prime numbers, encountered so far, and the hash table can potentially store all n elements of the input array.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!