Given two arrays arr[] and brr[] of size N such that the array brr[] consists of scores associated with corresponding elements of the array arr[]. The task is to find the maximum possible sum of assigned scores of a subsequence of numerically consecutive and distinct elements of the array arr[].
Examples:
Input: arr[] = {1, 2, 3, 3, 3, 1}, brr[] = {-1, 2, 10, 20, -10, -9}
Output: 22
Explanation:
Distinct values from the array = {1, 2, 3}
Maximum value assigned to each element = {1: -1, 2: 2, 3: 20}
Select the elements at index 2 and 4 in arr[] which are {2, 3}.
Maximum score = 2 + 20 = 22.Input: arr[] = {1, 2, 3, 2, 3, 1}, brr[] = {-1, 2, 10, 20, -10, -9}
Output: 32
Explanation: Selected subsequence is {arr[1], arr[2], arr[3]} = {2, 3, 2}
Naive Approach: The simplest approach to solve the problem is to use recursion. Follow the steps below to solve the problem:
- Generate all possible subsets of the given array arr[] such that the subset has unique and consecutive elements.
- While generating the subsets in the above step, there are two possibilities for every element of either being added to the subsequence or not. Therefore, follow the steps:
- If the current element is differed by 1 from the previously selected element, add the element to the subsequence.
- Otherwise, proceed to the next element.
- Update the maximum_score by considering both the above two possibilities.
- Print the final value of maximum_score obtained after the complete traversal of the array.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum score // with unique element in the subset int maximumSum( int a[], int b[], int n, int index, int lastpicked) { // Base Case if (index == n) return 0; int option1 = 0, option2 = 0; // Check if the previously picked // element differs by 1 from the // current element if (lastpicked == -1 || a[lastpicked] != a[index]) // Calculate score by including // the current element option1 = b[index] + maximumSum( a, b, n, index + 1, index); // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked); // Return maximum of the // two possibilities return max(option1, option2); } // Driver code int main() { // Given arrays int arr[] = { 1, 2, 3, 3, 3, 1 }; int brr[] = { -1, 2, 10, 20, -10, -9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call cout << (maximumSum(arr, brr, N, 0, -1)); } // This code is contributed by rutvik_56 |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the maximum score // with unique element in the subset public static int maximumSum( int [] a, int [] b, int n, int index, int lastpicked) { // Base Case if (index == n) return 0 ; int option1 = 0 , option2 = 0 ; // Check if the previously picked // element differs by 1 from the // current element if (lastpicked == - 1 || a[lastpicked] != a[index]) // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1 , index); // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1 , lastpicked); // Return maximum of the // two possibilities return Math.max(option1, option2); } // Driver Code public static void main(String[] args) { // Given arrays int arr[] = { 1 , 2 , 3 , 3 , 3 , 1 }; int brr[] = { - 1 , 2 , 10 , 20 , - 10 , - 9 }; int N = arr.length; // Function Call System.out.println( maximumSum(arr, brr, N, 0 , - 1 )); } } |
Python3
# Python3 program for the above approach # Function to find the maximum score # with unique element in the subset def maximumSum(a, b, n, index, lastpicked): # Base Case if (index = = n): return 0 option1 = 0 option2 = 0 # Check if the previously picked # element differs by 1 from the # current element if (lastpicked = = - 1 or a[lastpicked] ! = a[index]): # Calculate score by including # the current element option1 = b[index] + maximumSum(a, b, n, index + 1 , index) # Calculate score by excluding # the current element option2 = maximumSum(a, b, n, index + 1 , lastpicked) # Return maximum of the # two possibilities return max (option1, option2) # Driver Code if __name__ = = '__main__' : # Given arrays arr = [ 1 , 2 , 3 , 3 , 3 , 1 ] brr = [ - 1 , 2 , 10 , 20 , - 10 , - 9 ] N = len (arr) # Function call print (maximumSum(arr, brr, N, 0 , - 1 )) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approach using System; class GFG{ // Function to find the maximum score // with unique element in the subset public static int maximumSum( int [] a, int [] b, int n, int index, int lastpicked) { // Base Case if (index == n) return 0; int option1 = 0, option2 = 0; // Check if the previously picked // element differs by 1 from the // current element if (lastpicked == -1 || a[lastpicked] != a[index]) // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1, index); // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked); // Return maximum of the // two possibilities return Math.Max(option1, option2); } // Driver Code public static void Main(String[] args) { // Given arrays int []arr = {1, 2, 3, 3, 3, 1}; int []brr = {-1, 2, 10, 20, -10, -9}; int N = arr.Length; // Function Call Console.WriteLine(maximumSum(arr, brr, N, 0, -1)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement // the above approach // Function to find the maximum score // with unique element in the subset function maximumSum( a, b, n, index, lastpicked) { // Base Case if (index == n) return 0; let option1 = 0, option2 = 0; // Check if the previously picked // element differs by 1 from the // current element if (lastpicked == -1 || a[lastpicked] != a[index]) // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1, index); // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked); // Return maximum of the // two possibilities return Math.max(option1, option2); } // Driver code // Given arrays let arr = [ 1, 2, 3, 3, 3, 1 ]; let brr = [ -1, 2, 10, 20, -10, -9 ]; let N = arr.length; // Function Call document.write( maximumSum(arr, brr, N, 0, -1)); // This code is contributed by target_2. </script> |
22
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Efficient Approach: The above approach can be optimized by using Dynamic Programming as the problem has Overlapping Subproblems. Below are the steps:
- Initialize index as 0 and lastPicked as -1.
- Initialize a 2D array say dp[][] to store the result of the subproblems.
- The states of dp[][] will be the current index and last picked integer.
- Calculate the score for both possible options:
- Select the current element if the last picked integer is different from the current integer.
- Skip the current element and move on to the next element.
- Store the current state as the maximum of the value calculated above two-state.
- Print the value of dp[index][lastPicked + 1] as the result after all the recursive calls end.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // score possible int maximumSum( int a[], int b[], int n, int index, int lastpicked, vector<vector< int >> dp) { // Base Case if (index == n) return 0; // If previously occurred subproblem // occurred if (dp[index][lastpicked + 1] != -1) return dp[index][lastpicked + 1]; int option1 = 0, option2 = 0; // Check if lastpicked element differs // by 1 from the current element if (lastpicked == -1 || a[lastpicked] != a[index]) { // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1, index, dp); } // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked, dp); // Return maximum score from // the two possibilities return dp[index][lastpicked + 1] = max(option1, option2); } // Function to print maximum score void maximumPoints( int arr[], int brr[], int n) { int index = 0, lastPicked = -1; // DP array to store results // Initialise dp with -1 vector<vector< int >> dp(n + 5, vector< int >(n + 5, -1)); // Function call cout << maximumSum(arr, brr, n, index, lastPicked, dp) << endl; } // Driver code int main() { // Given arrays int arr[] = { 1, 2, 3, 3, 3, 1 }; int brr[] = { -1, 2, 10, 20, -10, -9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call maximumPoints(arr, brr, N); return 0; } // This code is contributed by divyeshrabadiya07 |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the maximum // score possible public static int maximumSum( int [] a, int [] b, int n, int index, int lastpicked, int [][] dp) { // Base Case if (index == n) return 0 ; // If previously occurred subproblem // occurred if (dp[index][lastpicked + 1 ] != - 1 ) return dp[index][lastpicked + 1 ]; int option1 = 0 , option2 = 0 ; // Check if lastpicked element differs // by 1 from the current element if (lastpicked == - 1 || a[lastpicked] != a[index]) { // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1 , index, dp); } // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1 , lastpicked, dp); // Return maximum score from // the two possibilities return dp[index][lastpicked + 1 ] = Math.max(option1, option2); } // Function to print maximum score public static void maximumPoints( int arr[], int brr[], int n) { int index = 0 , lastPicked = - 1 ; // DP array to store results int dp[][] = new int [n + 5 ][n + 5 ]; // Initialise dp with -1 for ( int i[] : dp) Arrays.fill(i, - 1 ); // Function call System.out.println( maximumSum(arr, brr, n, index, lastPicked, dp)); } // Driver Code public static void main(String[] args) { // Given arrays int arr[] = { 1 , 2 , 3 , 3 , 3 , 1 }; int brr[] = { - 1 , 2 , 10 , 20 , - 10 , - 9 }; int N = arr.length; // Function Call maximumPoints(arr, brr, N); } } |
Python3
# Python3 program for # the above approach # Function to find the # maximum score possible def maximumSum(a, b, n, index, lastpicked, dp): # Base Case if (index = = n): return 0 # If previously occurred # subproblem occurred if (dp[index][lastpicked + 1 ] ! = - 1 ): return dp[index][lastpicked + 1 ] option1, option2 = 0 , 0 # Check if lastpicked element differs # by 1 from the current element if (lastpicked = = - 1 or a[lastpicked] ! = a[index]): # Calculate score by including # the current element option1 = (b[index] + maximumSum(a, b, n, index + 1 , index, dp)) # Calculate score by excluding # the current element option2 = maximumSum(a, b, n, index + 1 , lastpicked, dp) # Return maximum score from # the two possibilities dp[index][lastpicked + 1 ] = max (option1, option2) return dp[index][lastpicked + 1 ] # Function to print maximum score def maximumPoints(arr, brr, n): index = 0 lastPicked = - 1 # DP array to store results dp = [[ - 1 for x in range (n + 5 )] for y in range (n + 5 )] # Function call print (maximumSum(arr, brr, n, index, lastPicked, dp)) # Driver Code if __name__ = = "__main__" : # Given arrays arr = [ 1 , 2 , 3 , 3 , 3 , 1 ] brr = [ - 1 , 2 , 10 , 20 , - 10 , - 9 ] N = len (arr) # Function Call maximumPoints(arr, brr, N) # This code is contributed by Chitranayal |
C#
// C# program for // the above approach using System; class GFG{ // Function to find the maximum // score possible public static int maximumSum( int [] a, int [] b, int n, int index, int lastpicked, int [,] dp) { // Base Case if (index == n) return 0; // If previously occurred // subproblem occurred if (dp[index, lastpicked + 1] != -1) return dp[index, lastpicked + 1]; int option1 = 0, option2 = 0; // Check if lastpicked element differs // by 1 from the current element if (lastpicked == -1 || a[lastpicked] != a[index]) { // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1, index, dp); } // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked, dp); // Return maximum score from // the two possibilities return dp[index, lastpicked + 1] = Math.Max(option1, option2); } // Function to print maximum score public static void maximumPoints( int []arr, int []brr, int n) { int index = 0, lastPicked = -1; // DP array to store results int [,]dp = new int [n + 5, n + 5]; // Initialise dp with -1 for ( int i = 0; i < n + 5; i++) { for ( int j = 0; j < n + 5; j++) { dp[i, j] = -1; } } // Function call Console.WriteLine(maximumSum(arr, brr, n, index, lastPicked, dp)); } // Driver Code public static void Main(String[] args) { // Given arrays int []arr = {1, 2, 3, 3, 3, 1}; int []brr = {-1, 2, 10, 20, -10, -9}; int N = arr.Length; // Function Call maximumPoints(arr, brr, N); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript program for the above approach // Function to find the maximum // score possible function maximumSum( a, b, n, index, lastpicked, dp) { // Base Case if (index == n) return 0; // If previously occurred subproblem // occurred if (dp[index][lastpicked + 1] != -1) return dp[index][lastpicked + 1]; let option1 = 0, option2 = 0; // Check if lastpicked element differs // by 1 from the current element if (lastpicked == -1 || a[lastpicked] != a[index]) { // Calculate score by including // the current element option1 = b[index] + maximumSum(a, b, n, index + 1, index, dp); } // Calculate score by excluding // the current element option2 = maximumSum(a, b, n, index + 1, lastpicked, dp); // Return maximum score from // the two possibilities return dp[index][lastpicked + 1] = Math.max(option1, option2); } // Function to print maximum score function maximumPolets( arr, brr, n) { let index = 0, lastPicked = -1; // DP array to store results let dp = new Array(n + 5); // Loop to create 2D array using 1D array for ( var i = 0; i < dp.length; i++) { dp[i] = new Array(2); } // Initialise dp with -1 for ( var i = 0; i < dp.length; i++) { for ( var j = 0; j < dp.length; j++) { dp[i][j] = -1; } } // Function call document.write( maximumSum(arr, brr, n, index, lastPicked, dp)); } // Driver Code // Given arrays let arr = [ 1, 2, 3, 3, 3, 1 ]; let brr = [ -1, 2, 10, 20, -10, -9 ]; let N = arr.length; // Function Call maximumPolets(arr, brr, N); </script> |
22
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Efficient approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Steps to solve this problem :
- Create a table DP to store the solution of the subproblems and initialize it with 0.
- Initialize the table with base cases.
- Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
- Initialize a variable maxScore with 0 because it compare and store maximum value.
- Now iterate over dp and get the maximum value and store it in maxScore.
- At last print the final solution stored in maxScore.
Implementation :
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum score possible void maximumPoints( int arr[], int brr[], int n) { // DP table to store results int dp[n + 5][n + 5]; // Initialise DP table with 0 memset (dp, 0, sizeof (dp)); // Loop through all indices and their previous index for ( int i = 1; i <= n; i++) { for ( int j = 0; j < i; j++) { // Check if previous index value differs by 1 if (j == 0 || arr[j - 1] != arr[i - 1]) { // Calculate score by including current element dp[i][j] = max(dp[i][j], dp[j][0] + brr[i - 1]); } // Calculate score by excluding current element dp[i][i - 1] = max(dp[i][i - 1], dp[j][i - j - 1]); } } // Find maximum score int maxScore = 0; for ( int i = 0; i <= n; i++) { for ( int j = 0; j <= n; j++) { maxScore = max(maxScore, dp[i][j]); } } // Print maximum score cout << maxScore << endl; } // Driver code int main() { // Given arrays int arr[] = { 1, 2, 3, 3, 3, 1 }; int brr[] = { -1, 2, 10, 20, -10, -9 }; int N = sizeof (arr) / sizeof (arr[0]); // Function call maximumPoints(arr, brr, N); return 0; } // this code is contributed by bhardwajji |
Python3
# Function to find the maximum score possible def maximumPoints(arr, brr, n): # DP table to store results dp = [[ 0 for j in range (n + 5 )] for i in range (n + 5 )] # Loop through all indices and their previous index for i in range ( 1 , n + 1 ): for j in range (i): # Check if previous index value differs by 1 if j = = 0 or arr[j - 1 ] ! = arr[i - 1 ]: # Calculate score by including current element dp[i][j] = max (dp[i][j], dp[j][ 0 ] + brr[i - 1 ]) # Calculate score by excluding current element dp[i][i - 1 ] = max (dp[i][i - 1 ], dp[j][i - j - 1 ]) # Find maximum score maxScore = 0 for i in range (n + 1 ): for j in range (n + 1 ): maxScore = max (maxScore, dp[i][j]) # Print maximum score print (maxScore) # Given arrays arr = [ 1 , 2 , 3 , 3 , 3 , 1 ] brr = [ - 1 , 2 , 10 , 20 , - 10 , - 9 ] N = len (arr) # Function call maximumPoints(arr, brr, N) |
C#
using System; public class Program { // Function to find the maximum score possible public static void MaximumPoints( int [] arr, int [] brr, int n) { // DP table to store results int [, ] dp = new int [n + 5, n + 5]; // Initialise DP table with 0 for ( int i = 0; i < n + 5; i++) { for ( int j = 0; j < n + 5; j++) { dp[i, j] = 0; } } // Loop through all indices and their previous index for ( int i = 1; i <= n; i++) { for ( int j = 0; j < i; j++) { // Check if previous index value differs by // 1 if (j == 0 || arr[j - 1] != arr[i - 1]) { // Calculate score by including current // element dp[i, j] = Math.Max( dp[i, j], dp[j, 0] + brr[i - 1]); } // Calculate score by excluding current // element dp[i, i - 1] = Math.Max(dp[i, i - 1], dp[j, i - j - 1]); } } // Find maximum score int maxScore = 0; for ( int i = 0; i <= n; i++) { for ( int j = 0; j <= n; j++) { maxScore = Math.Max(maxScore, dp[i, j]); } } // Print maximum score Console.WriteLine(maxScore); } // Driver code public static void Main() { // Given arrays int [] arr = { 1, 2, 3, 3, 3, 1 }; int [] brr = { -1, 2, 10, 20, -10, -9 }; int n = arr.Length; // Function call MaximumPoints(arr, brr, n); } } // This code is contritbuted by sarojmcy2e |
Javascript
function maximumPoints(arr, brr, n) { // DP table to store results const dp = Array.from({ length: n + 5 }, () => Array(n + 5).fill(0)); // Loop through all indices and their previous index for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { // Check if previous index value differs by 1 if (j === 0 || arr[j - 1] !== arr[i - 1]) { // Calculate score by including current element dp[i][j] = Math.max(dp[i][j], dp[j][0] + brr[i - 1]); } // Calculate score by excluding current element dp[i][i - 1] = Math.max(dp[i][i - 1], dp[j][i - j - 1]); } } // Find maximum score let maxScore = 0; for (let i = 0; i <= n; i++) { for (let j = 0; j <= n; j++) { maxScore = Math.max(maxScore, dp[i][j]); } } // Print maximum score console.log(maxScore); } // Given arrays const arr = [1, 2, 3, 3, 3, 1]; const brr = [-1, 2, 10, 20, -10, -9]; const n = arr.length; // Function call maximumPoints(arr, brr, n); // This code is contributed by user_dtewbxkn77n |
Java
import java.util.*; class Main { // Function to find the maximum score possible static void maximumPoints( int arr[], int brr[], int n) { // DP table to store results int dp[][] = new int [n + 5 ][n + 5 ]; // Initialise DP table with 0 for ( int i = 0 ; i < n + 5 ; i++) { Arrays.fill(dp[i], 0 ); } // Loop through all indices and //their previous index for ( int i = 1 ; i <= n; i++) { for ( int j = 0 ; j < i; j++) { // Check if previous index // value differs by 1 if (j == 0 || arr[j - 1 ] != arr[i - 1 ]) { // Calculate score by including // the current element dp[i][j] = Math.max( dp[i][j], dp[j][ 0 ] + brr[i - 1 ]); } // Calculate score by excluding // current element dp[i][i - 1 ] = Math.max(dp[i][i - 1 ], dp[j][i - j - 1 ]); } } // Find maximum score int maxScore = 0 ; for ( int i = 0 ; i <= n; i++) { for ( int j = 0 ; j <= n; j++) { maxScore = Math.max(maxScore, dp[i][j]); } } // Print maximum score System.out.println(maxScore); } // Driver Code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 3 , 3 , 1 }; int brr[] = { - 1 , 2 , 10 , 20 , - 10 , - 9 }; int N = arr.length; maximumPoints(arr, brr, N); } } |
22
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!