Given an array arr[] of size N, the task is to find the maximum possible sum of a subset of the array such that no two consecutive elements are part of the subset.
Examples:
Input: arr[]= {2, 3, 2, 3, 3, 4}
Output: 9
Explanation: The subset having all the 3s i.e. {3, 3, 3} have sum = 9.
This is the maximum possible sum of any possible subset of the array following the condition.Input: arr[] = {2, 3, 4}
Output: 6
Explanation: The subset is {2, 4}. It has sum = 6 which is the maximum possible.
Naive Approach: The naive approach is to generate all the possible subsets and from them check which subsets are following the given condition. Calculate the sum of those subsets and the maximum among them is the required answer.
Time Complexity: O(2N)
Auxiliary Space: O(2N)
Efficient Approach: An efficient approach is to use dynamic programming with the help of the following idea:
For any element X in arr[], the value X-1 cannot be considered but all the elements having value X can be. So for X the maximum possible answer till X is maximum between (maximum possible answer till X-2 + freq(X)*X) and (maximum possible answer till X-1)
Follow the steps mentioned below to solve the problem:
- Use hashing to store the frequency of each element.
- Find the maximum value of the array. (say X)
- Create a dp[] array where dp[i] stores the maximum possible subset sum when elements with value at most i are included in the subset.
- Iterate from i = 2 to X of the array:
- Calculate the value of dp[i] as per the formula from the observation dp[i] = max(dp[i-2] + i*freq(i), dp[i-1]).
- The maximum value from the dp[] array is the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the maximum valueint MaximiseStockPurchase(vector<int>& nums, int n){ int maxi = 0; for (int i = 0; i < n; i++) maxi = max(maxi, nums[i]); vector<int> freq(maxi + 1, 0); vector<int> dp(maxi + 1, 0); for (auto i : nums) freq[i]++; dp[1] = freq[1]; // Loop to calculate dp[] array // till max element of array for (int i = 2; i <= maxi; i++) dp[i] = max(dp[i - 2] + i * freq[i], dp[i - 1]); return dp[maxi];}// Driver codeint main(){ vector<int> arr{ 2, 2, 3, 4, 3, 3 }; int N = arr.size(); int res = MaximiseStockPurchase(arr, N); cout << res; return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to calculate the maximum value static int MaximiseStockPurchase(int nums[], int n) { int maxi = 0; for (int i = 0; i < n; i++) maxi = Math.max(maxi, nums[i]); int freq[] = new int[maxi + 1]; int dp[] = new int[maxi + 1]; for (int i = 0; i < n; i++) freq[nums[i]]++; dp[1] = freq[1]; // Loop to calculate dp[] array // till max element of array for (int i = 2; i <= maxi; i++) dp[i] = Math.max(dp[i - 2] + i * freq[i], dp[i - 1]); return dp[maxi]; } // Driver code public static void main (String[] args) { int arr[] = { 2, 2, 3, 4, 3, 3 }; int N = arr.length; int res = MaximiseStockPurchase(arr, N); System.out.println(res); }}// This code is contributed by hrithikgarg03188. |
Python3
# Python 3 code to implement the approach# Function to calculate the maximum valuedef MaximiseStockPurchase(nums, n): maxi = 0 for i in range(n): maxi = max(maxi, nums[i]) freq = [0]*(maxi + 1) dp = [0] * (maxi + 1) for i in nums: freq[i] += 1 dp[1] = freq[1] # Loop to calculate dp[] array # till max element of array for i in range(2, maxi + 1): dp[i] = max(dp[i - 2] + i * freq[i], dp[i - 1]) return dp[maxi]# Driver codeif __name__ == "__main__": arr = [2, 2, 3, 4, 3, 3] N = len(arr) res = MaximiseStockPurchase(arr, N) print(res) # This code is contributed by ukasp. |
C#
// C# code to implement the approachusing System;class GFG { // Function to calculate the maximum value static int MaximiseStockPurchase(int[] nums, int n) { int maxi = 0; for (int i = 0; i < n; i++) maxi = Math.Max(maxi, nums[i]); int[] freq = new int[maxi + 1]; int[] dp = new int[maxi + 1]; for (int i = 0; i < n; i++) freq[nums[i]]++; dp[1] = freq[1]; // Loop to calculate dp[] array // till max element of array for (int i = 2; i <= maxi; i++) dp[i] = Math.Max(dp[i - 2] + i * freq[i], dp[i - 1]); return dp[maxi]; } // Driver code public static void Main() { int[] arr = { 2, 2, 3, 4, 3, 3 }; int N = arr.Length; int res = MaximiseStockPurchase(arr, N); Console.WriteLine(res); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code to implement the approach // Function to calculate the maximum value const MaximiseStockPurchase = (nums, n) => { let maxi = 0; for (let i = 0; i < n; i++) maxi = Math.max(maxi, nums[i]); let freq = new Array(maxi + 1).fill(0); let dp = new Array(maxi + 1).fill(0); for (let i in nums) freq[nums[i]]++; dp[1] = freq[1]; // Loop to calculate dp[] array // till max element of array for (let i = 2; i <= maxi; i++) dp[i] = Math.max(dp[i - 2] + i * freq[i], dp[i - 1]); return dp[maxi]; } // Driver code let arr = [2, 2, 3, 4, 3, 3]; let N = arr.length; let res = MaximiseStockPurchase(arr, N); document.write(res);// This code is contributed by rakeshsahni</script> |
Output
9
Time Complexity: O(M) where M is the maximum element of the array.
Auxiliary Space: O(M)
Alternative Approach: In the above approach the space of the dp[] array can be optimized as below:
As seen from the observation we only need the value of dp[i-1] and dp[i-2] to calculate the value of dp[i]. So instead of using dp[] array use two variables to store the value of the previous two steps.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the maximum sumint MaximiseStockPurchase(vector<int>& nums, int n){ int maxNum = INT_MIN; for (auto i : nums) maxNum = max(maxNum, i); vector<int> freq(maxNum + 1, 0); for (auto i : nums) freq[i]++; int curPoints = freq[1], prevPoints = 0; // Loop to calculate the sum for (int i = 2; i <= maxNum; i++) { int tmp = curPoints; curPoints = max(prevPoints + i * freq[i], curPoints); prevPoints = tmp; } return curPoints;}// Driver codeint main(){ vector<int> arr{ 2, 2, 3, 4, 3, 3 }; int N = arr.size(); int res = MaximiseStockPurchase(arr, N); cout << res; return 0;} |
Java
// Java implementation of above approachimport java.io.*;import java.util.*;class GFG { // Function to calculate the maximum sum static int MaximiseStockPurchase(int[] nums, int n) { int maxNum = Integer.MIN_VALUE; for(int i : nums) maxNum = Math.max(maxNum, i); int[] freq = new int[maxNum + 1]; for (int x = 0; x < maxNum; x++) { freq[x] = 0; } for(int i : nums) freq[i]++; int curPoints = freq[1], prevPoints = 0; // Loop to calculate the sum for (int i = 2; i <= maxNum; i++) { int tmp = curPoints; curPoints = Math.max(prevPoints + i * freq[i], curPoints); prevPoints = tmp; } return curPoints; } // Driver Code public static void main(String[] args) { int[] arr = { 2, 2, 3, 4, 3, 3 }; int N = arr.length; int res = MaximiseStockPurchase(arr, N); System.out.print(res); }}// This code is contributed by code_hunt. |
Python3
# Python code to implement the approach# Function to calculate the maximum sumimport sysdef MaximiseStockPurchase(nums,n): maxNum = -sys.maxsize -1 for i in nums: maxNum = max(maxNum, i) freq = [0 for i in range(maxNum+1)] for i in nums: freq[i] += 1 curPoints,prevPoints = freq[1],0 # Loop to calculate the sum for i in range(2,maxNum+1): tmp = curPoints curPoints = max(prevPoints + i * freq[i],curPoints) prevPoints = tmp return curPoints# Driver codearr = [ 2, 2, 3, 4, 3, 3 ]N = len(arr)res = MaximiseStockPurchase(arr, N)print(res)# This code is contributed by shinjanpatra |
C#
// C# code to implement the approachusing System;class GFG { // Function to calculate the maximum sum static int MaximiseStockPurchase(int[] nums, int n) { int maxNum = Int32.MinValue; foreach(int i in nums) maxNum = Math.Max(maxNum, i); int[] freq = new int[maxNum + 1]; for (int x = 0; x < maxNum; x++) { freq[x] = 0; } foreach(int i in nums) freq[i]++; int curPoints = freq[1], prevPoints = 0; // Loop to calculate the sum for (int i = 2; i <= maxNum; i++) { int tmp = curPoints; curPoints = Math.Max(prevPoints + i * freq[i], curPoints); prevPoints = tmp; } return curPoints; } // Driver code public static void Main() { int[] arr = { 2, 2, 3, 4, 3, 3 }; int N = arr.Length; int res = MaximiseStockPurchase(arr, N); Console.Write(res); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript code to implement the approach// Function to calculate the maximum sumfunction MaximiseStockPurchase(nums,n){ let maxNum = Number.MIN_VALUE; for (let i of nums) maxNum = Math.max(maxNum, i); let freq = new Array(maxNum + 1).fill(0); for (let i of nums) freq[i]++; let curPoints = freq[1], prevPoints = 0; // Loop to calculate the sum for (let i = 2; i <= maxNum; i++) { let tmp = curPoints; curPoints = Math.max(prevPoints + i * freq[i], curPoints); prevPoints = tmp; } return curPoints;}// Driver codelet arr = [ 2, 2, 3, 4, 3, 3 ];let N = arr.length;let res = MaximiseStockPurchase(arr, N);document.write(res);// This code is contributed by shinjanpatra</script> |
Output
9
Time complexity: O(N + M) where M is the maximum element of the array
Auxiliary Space: O(M).
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!
