Maximum sum of Subset having no consecutive elements

By Stephen Roberts On Mar 14, 2022

Dive into summer with a Google Nest Thermostat for $100 during…

Get the Bose QuietComfort 2 earbuds for $80 less through…

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(2^N)
Auxiliary Space: O(2^N)

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++

#include <bits/stdc++.h>

using namespace std;

int 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];

for (int i = 2; i <= maxi; i++)

dp[i] = max(dp[i - 2] + i * freq[i],

dp[i - 1]);

return dp[maxi];

}

int main()

{

vector<int> arr{ 2, 2, 3, 4, 3, 3 };

int N = arr.size();

int res = MaximiseStockPurchase(arr, N);

cout << res;

return 0;

}

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++

#include <bits/stdc++.h>

using namespace std;

int 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;

for (int i = 2; i <= maxNum; i++) {

int tmp = curPoints;

curPoints = max(prevPoints + i * freq[i],

curPoints);

prevPoints = tmp;

}

return curPoints;

}

int main()

{

vector<int> arr{ 2, 2, 3, 4, 3, 3 };

int N = arr.size();

int res = MaximiseStockPurchase(arr, N);

cout << res;

return 0;

}

Time complexity: O(N + M) where M is the maximum element of the array
Auxiliary Space: O(M).

Read original article here

Denial of responsibility! News Leaflets is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.