2

Maximum sum of a Subarray with prime integers

 1 year ago
source link: https://www.geeksforgeeks.org/maximum-sum-of-a-subarray-with-prime-integers/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Maximum sum of a Subarray with prime integers

gauravprajapat24012001

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
  • Return maxSum

Below is the code to implement the above steps:

  • Python3
  • Javascript
// 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;
}
Output
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:

  • Python3
  • Javascript
// 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;
}
Output
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.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK