Given an array arr[] of size N, the task is to find the maximum sum of a subsequence formed by concatenating disjoint subarrays whose lengths are prime numbers.
Examples:
Input: arr[] = {10, 10, 7, 10, 10, 10}
Output: 50
Explanation:
Subsequence with maximum sum is obtained by concatenating following two subarrays:
- {10, 10} of length 2, which is prime.
- {10, 10, 10} of length 3, which is prime.
The resulting subsequence is {10, 10, 10, 10, 10}.
Sum of the subsequence is 50.Input: arr[] = {11, 8, 12}
Output: 31
Naive Approach: The simplest approach is to use recursion to calculate the value of the maximum sum of subsequence. In each step, call multiple recursive calls for each of the prime numbers smaller than N. The recurrence relation is given by:
sum(N) = (arr[N] + arr[N – 1] + … arr[N – P + 1]) + sum(N – P – 1)
where,
P is the prime length of the subarray chosen,
sum(N) is the function that finds the maximum sum of resulting subsequence.
The above recurrence relation is for only one Prime Number. Therefore, there can be more than one possible subsequence can be formed by selecting different subarrays of different prime length. Below is the resulting recurrence relation formed:
sum(N) = max(sum(aN, …, aN-P1+1) + sum(N – P1 – 1), sum(aN, …, aN-P2+1) + sum(N – P2 – 1), …, sum(aN, …, aN-Pk+1) + sum(N – Pk – 1))
where,
P1, P2, … Pk are prime numbers smaller than N.
Time Complexity: O(KN) where K is the number of the prime numbers smaller than N. Approximately K = (N / LogN)
Auxiliary Space: O(1)
Dynamic Programming using Bottom-up Approach: The recursive calls in the above can also be reduced using an auxiliary array dp[] and calculate the value of each state in the bottom-up approach. Below are the steps:
- Create an auxiliary array prime[] to store all the prime numbers smaller or equal to N.
- Maintain the Sieve of Eratosthenes and traverse it to populate the values of array prime[].
- Create an auxiliary array dp[] of size N.
- Initialize the state 0 and 1 as dp[0] = 0 and dp[1] = 0.
- Traverse the array dp[] over the range [2, N] and update each state as:
MSS(i) = max[sum(ai…ai-P1+1) + sum(i-P1-1), sum(ai…ai-P2+1) + sum(i-P2-1), … sum(ai…ai-Pk+1) + sum(i-Pk-1) ] for all prime numbers P1, P2, … Pk smaller than N.
- Initialize pref[] array to store prefix sum to calculate sum(l, …, r) efficiently.
ai + ai+1 + … aj = sum(i … j) = pref[j] – pref[i – 1]
- Print the value of dp[N] after the above steps as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAX 100005// Function to return all prime numbers// smaller than Nvector<int> SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" bool sieve[MAX]; // Initialize all its entries as true memset(sieve, true, sizeof(sieve)); for (int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (sieve[p] == true) { // Update all multiples of // p greater than or equal // to the square of it for (int i = p * p; i < MAX; i += p) { sieve[i] = false; } } } // Stores all prime numbers // smaller than MAX vector<int> v; // Store all prime numbers for (int p = 2; p < MAX; p++) { // If p is prime if (sieve[p]) { v.push_back(p); } } return v;}// Function to build the auxiliary DP// array from the startvoid build(int dp[], int arr[], int N){ // Base Case dp[0] = 0; dp[1] = 0; // Stores all prime numbers < N vector<int> prime = SieveOfEratosthenes(); // Stores prefix sum int pref[N + 1]; pref[0] = 0; // Update prefix sum for (int i = 1; i <= N; i++) { pref[i] = pref[i - 1] + arr[i - 1]; } // Iterate over range for (int i = 2; i <= N; i++) { // Update each state i.e.. when // current element is excluded dp[i] = dp[i - 1]; for (int j = 0; j <= prime.size(); j++) { // Find start & end index // of subarrays when prime[i] // is taken int r = i - 1; int l = r - prime[j] + 1; // Check if starting point // lies in the array if (l < 0) break; int temp = 0; // Include the elements // al al+1 ... ar temp = pref[r + 1] - pref[l]; // Check if element lies before // start of selected subarray if (l - 2 >= 0) temp += dp[l - 2 + 1]; // Update value of dp[i] dp[i] = max(dp[i], temp); } }}// Function to find the maximum sum// subsequence with prime lengthvoid maxSumSubseq(int arr[], int N){ // Auxiliary DP array int dp[N + 1]; // Build DP array build(dp, arr, N); // Print the result cout << dp[N];}// Driver Codeint main(){ // Given arr[] int arr[] = { 10, 10, 7, 10, 10, 10 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); // Function Call maxSumSubseq(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int MAX = 100005;// Function to return all prime numbers// smaller than Nstatic Vector<Integer> SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" boolean []sieve = new boolean[MAX]; // Initialize all its entries as true Arrays.fill(sieve, true); for(int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (sieve[p] == true) { // Update all multiples of // p greater than or equal // to the square of it for(int i = p * p; i < MAX; i += p) { sieve[i] = false; } } } // Stores all prime numbers // smaller than MAX Vector<Integer> v = new Vector<Integer>(); // Store all prime numbers for(int p = 2; p < MAX; p++) { // If p is prime if (sieve[p]) { v.add(p); } } return v;}// Function to build the auxiliary DP// array from the startstatic void build(int dp[], int arr[], int N){ // Base Case dp[0] = 0; dp[1] = 0; // Stores all prime numbers < N Vector<Integer> prime = SieveOfEratosthenes(); // Stores prefix sum int []pref = new int[N + 1]; pref[0] = 0; // Update prefix sum for(int i = 1; i <= N; i++) { pref[i] = pref[i - 1] + arr[i - 1]; } // Iterate over range for(int i = 2; i <= N; i++) { // Update each state i.e.. when // current element is excluded dp[i] = dp[i - 1]; for(int j = 0; j <= prime.size(); j++) { // Find start & end index // of subarrays when prime[i] // is taken int r = i - 1; int l = r - prime.get(j) + 1; // Check if starting point // lies in the array if (l < 0) break; int temp = 0; // Include the elements // al al+1 ... ar temp = pref[r + 1] - pref[l]; // Check if element lies before // start of selected subarray if (l - 2 >= 0) temp += dp[l - 2 + 1]; // Update value of dp[i] dp[i] = Math.max(dp[i], temp); } }}// Function to find the maximum sum// subsequence with prime lengthstatic void maxSumSubseq(int arr[], int N){ // Auxiliary DP array int []dp = new int[N + 1]; // Build DP array build(dp, arr, N); // Print the result System.out.print(dp[N]);}// Driver Codepublic static void main(String args[]){ // Given arr[] int arr[] = { 10, 10, 7, 10, 10, 10 }; // Size of array int N = arr.length; // Function Call maxSumSubseq(arr, N);}}// This code is contributed by ipg2016107 |
Python3
# Python3 program for the above approachMAX = 100005# Function to return all prime numbers# smaller than Ndef SieveOfEratosthenes(): # Create a boolean array "prime[0..n]" sieve = [True for i in range(MAX)] # Initialize all its entries as true # memset(sieve, true, sizeof(sieve)) for p in range(2, MAX): if p * p > MAX: break # If prime[p] is not changed, # then it is a prime if (sieve[p] == True): # Update all multiples of # p greater than or equal # to the square of it for i in range(p * p, MAX, p): sieve[i] = False # Stores all prime numbers # smaller than MAX v = [] # Store all prime numbers for p in range(2, MAX): # If p is prime if (sieve[p]): v.append(p) return v# Function to build the auxiliary DP# array from the startdef build(dp, arr, N): # Base Case dp[0] = 0 dp[1] = 0 # Stores all prime numbers < N prime = SieveOfEratosthenes() # Stores prefix sum pref = [0 for i in range(N + 1)] pref[0] = 0 # Update prefix sum for i in range(1, N + 1): pref[i] = pref[i - 1] + arr[i - 1] # Iterate over range for i in range(2, N + 1): # Update each state i.e.. when # current element is excluded dp[i] = dp[i - 1] for j in range(len(prime) + 1): # Find start & end index # of subarrays when prime[i] # is taken r = i - 1 l = r - prime[j] + 1 # Check if starting point # lies in the array if (l < 0): break temp = 0 # Include the elements # al al+1 ... ar temp = pref[r + 1] - pref[l] # Check if element lies before # start of selected subarray if (l - 2 >= 0): temp += dp[l - 2 + 1] # Update value of dp[i] dp[i] = max(dp[i], temp)# Function to find the maximum sum# subsequence with prime lengthdef maxSumSubseq(arr, N): # Auxiliary DP array dp = [0 for i in range(N + 1)] # Build DP array build(dp, arr, N) # Print the result print(dp[N])# Driver Codeif __name__ == '__main__': # Given arr[] arr = [ 10, 10, 7, 10, 10, 10 ] # Size of array N = len(arr) # Function Call maxSumSubseq(arr, N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{ static int MAX = 100005;// Function to return all// prime numbers smaller than Nstatic List<int> SieveOfEratosthenes(){ // Create a bool array // "prime[0..n]" bool []sieve = new bool[MAX]; // Initialize all its entries // as true for(int i = 0; i < MAX; i++) sieve[i] = true; for(int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (sieve[p] == true) { // Update all multiples of // p greater than or equal // to the square of it for(int i = p * p; i < MAX; i += p) { sieve[i] = false; } } } // Stores all prime numbers // smaller than MAX List<int> v = new List<int>(); // Store all prime numbers for(int p = 2; p < MAX; p++) { // If p is prime if (sieve[p]) { v.Add(p); } } return v;}// Function to build the auxiliary // DP array from the startstatic void build(int []dp, int []arr, int N){ // Base Case dp[0] = 0; dp[1] = 0; // Stores all prime // numbers < N List<int> prime = SieveOfEratosthenes(); // Stores prefix sum int []pref = new int[N + 1]; pref[0] = 0; // Update prefix sum for(int i = 1; i <= N; i++) { pref[i] = pref[i - 1] + arr[i - 1]; } // Iterate over range for(int i = 2; i <= N; i++) { // Update each state i.e.. // when current element // is excluded dp[i] = dp[i - 1]; for(int j = 0; j <= prime.Count; j++) { // Find start & end index // of subarrays when prime[i] // is taken int r = i - 1; int l = r - prime[j] + 1; // Check if starting point // lies in the array if (l < 0) break; int temp = 0; // Include the elements // al al+1 ... ar temp = pref[r + 1] - pref[l]; // Check if element lies // before start of selected // subarray if (l - 2 >= 0) temp += dp[l - 2 + 1]; // Update value of dp[i] dp[i] = Math.Max(dp[i], temp); } }}// Function to find the maximum // sum subsequence with prime // lengthstatic void maxSumSubseq(int []arr, int N){ // Auxiliary DP array int []dp = new int[N + 1]; // Build DP array build(dp, arr, N); // Print the result Console.Write(dp[N]);}// Driver Codepublic static void Main(String []args){ // Given []arr int []arr = {10, 10, 7, 10, 10, 10}; // Size of array int N = arr.Length; // Function Call maxSumSubseq(arr, N);}}// This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approachlet MAX = 100005// Function to return all prime numbers// smaller than Nfunction SieveOfEratosthenes(){ // Create a boolean array "prime[0..n]" let sieve = new Array(MAX); // Initialize all its entries as true sieve.fill(true) for (let p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (sieve[p] == true) { // Update all multiples of // p greater than or equal // to the square of it for (let i = p * p; i < MAX; i += p) { sieve[i] = false; } } } // Stores all prime numbers // smaller than MAX let v = new Array(); // Store all prime numbers for (let p = 2; p < MAX; p++) { // If p is prime if (sieve[p]) { v.push(p); } } return v;}// Function to build the auxiliary DP// array from the startfunction build(dp, arr, N){ // Base Case dp[0] = 0; dp[1] = 0; // Stores all prime numbers < N let prime = SieveOfEratosthenes(); // Stores prefix sum let pref = new Array(N + 1); pref[0] = 0; // Update prefix sum for (let i = 1; i <= N; i++) { pref[i] = pref[i - 1] + arr[i - 1]; } // Iterate over range for (let i = 2; i <= N; i++) { // Update each state i.e.. when // current element is excluded dp[i] = dp[i - 1]; for (let j = 0; j <= prime.length; j++) { // Find start & end index // of subarrays when prime[i] // is taken let r = i - 1; let l = r - prime[j] + 1; // Check if starting point // lies in the array if (l < 0) break; let temp = 0; // Include the elements // al al+1 ... ar temp = pref[r + 1] - pref[l]; // Check if element lies before // start of selected subarray if (l - 2 >= 0) temp += dp[l - 2 + 1]; // Update value of dp[i] dp[i] = Math.max(dp[i], temp); } }}// Function to find the maximum sum// subsequence with prime lengthfunction maxSumSubseq(arr, N){ // Auxiliary DP array let dp = new Array(N + 1); // Build DP array build(dp, arr, N); // Print the result document.write(dp[N]);}// Driver Code // Given arr[] let arr = [ 10, 10, 7, 10, 10, 10 ]; // Size of array let N = arr.length; // Function Call maxSumSubseq(arr, N);// This code is contributed by gfgking</script> |
Output
50
Time Complexity: O(N * K)
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!
