Algorithm:

1) Find the maximum number max in the array.
2) Create a new auxiliary array dp of size max+1 and store frequencies of unique elements in the array, where dp[i] denotes the number of times i ...read more

The key point to notice here is that in the given problem that we don’t need to delete anything from the array while selecting arr[i] from the array. We just only care about whether we select any number arr[i] from the array then we cant select the arr[i]+1 and arr[i]-1 from the array to maximize the sum in the next steps. So we will find the maximum number max in the array and create a new auxiliary array of the size max+1 that stores the number of occurrences of each unique element in the array. The count is stored in an auxiliary array at their respective index. 

Now the problem is to find the maximum sum of a subsequence of the array where the subsequence does not contain adjacent elements of the array. This problem is similar to the  0/1 Knapsack Problem in which in the recursion call at any index, we have two choices whether to include that element in sum or exclude that element. Now if we choose the current number to add to the sum then recur for index i+2  or If we don’t choose the current index then recur for index i+1 and this way we find the maximum sum.

Algorithm:

1. Find the maximum number max in the array.
2. Create a new auxiliary array freq of size max+1 and store frequencies of unique elements in the array, where freq[id] denotes the number of times ‘id’ as an element is present in the input array.
3. Define and call a helper function, maximumSumHelper(freq[], id) to calculate the maximum possible sum where freq is the frequency array and id denotes the current index of this freq array and return maximumSumHelper(freq, 0).

long maximumSumHelper(freq[], id):

1. If id reaches the end of freq array, return 0.
2. Then we have two choices:
   1. id * freq[id] + maximumSumHelper(freq, id + 2)
   2. maximumSumHelper(freq, id + 1);
3. Then return the maximum of both.

O(MAX), where “MAX” is the maximum element present in the array.

In the worst case, extra space is required to create the auxiliary array of size MAX, and also for the recursion stack.

O(2^MAX), where “MAX” is the maximum element present and N is the size of the array.

In the worst case, we will find the maximum element in an array that takes O(N) time. For every index of the freq array, we have two choices i.e either to include that element or exclude the element. Thus the overall running time will be O(2^MAX + N).   

• The previous approach uses recursion which has many overlapping subproblems. i.e recursive function computes the same sub-problems again and again. So we can use memoization to overcome the overlapping subproblems.
• To reiterate memoization is when we store the results in a lookup array(dp) of all previously solved subproblems and use the results from the dp if we encounter the problem that has already been solved.
• Since there is only one state which is changing in the recursive function maximumSumHelper() i.e id  So we use the 1-dimensional array dp[] to store all the subproblems. And dp[id] will store the maximum possible sum from the starting index till id index.

Algorithm:

1. Find the maximum number max in the array.
2. Create a new auxiliary array freq of size max+1 and store frequencies of unique elements in the array, where freq[id] denotes the number of times ‘id’ as an element is present in the input array.
3. Define and call a helper function, maximumSumHelper(freq[], id, dp[]) to calculate the maximum possible sum where freq is the frequency array, id denotes the current index of this freq array and dp represents the lookup array and return maximumSumHelper(freq, 0, dp).

long maximumSumHelper(freq[], id, dp[]):

1. If id reaches the end of freq array, return 0.
2. If we already solve the same subproblem for index id, return dp[id].
3. Otherwise we have two choices:
4. id * ans[id] + maximumSumHelper(ans, id + 2)
5. maximumSumHelper(ans, id + 1);
6. Then store the maximum of both in dp[id] and return dp[id].

O(MAX), where “MAX” is the maximum element present in the array.

In the worst case, extra space is required to create the freq and dp array of size MAX i.e O(MAX) and also for the recursion stack. Hence the overall complexity will be O(MAX). 

O(max(MAX, N)), where “MAX” is the maximum element present and N is the size of the array.

In the worst case, we will find the maximum element in the array “arr” that takes O(N) time. The array dp stores the results for all the subproblems, we can conclude that we will not have more than MAX subproblems therefore it takes O(MAX). Hence the overall complexity will be O(max(MAX, N)),

The idea is to use a bottom-up dynamic programming approach instead of a memoization approach. In this, we also have two choices whether to select or not. If we select then we take ...read more