Last Updated: 28 Jan, 2021
Maximum Sum Increasing Subsequence
Moderate
Asked in companies
Ninja has recently joined the gym. He decides to lift dumbbells to build muscles. The rack contains dumbbells with varying weights. His strategy is to pick a dumbbell randomly from the rack and after exercising place it back to its original position. Now for the next exercise he can only pick dumbbells that are heavier and positioned right to the previously used. After completing all the exercises he has to tell the sum of weights of all dumbbells he picked to his trainer.
In order to impress his trainer he wants this sum to be as maximum as possible. As Ninja is saving energy for exercises, he asks you to help him choose dumbbells. Can you help Ninja to impress his trainer?
For example:
If the ‘RACK’ contains dumbbells with weights [5, 1, 2, 8], then the possible ways to choose dumbbells according to the given conditions are: [ 5 ], [ 1 ], [ 2 ], [ 8 ], [ 5, 8 ], [ 1, 2 ], [ 1, 2, 8 ], [ 2, 8 ]. Lifting dumbbells with weights [ 5, 8 ] gives the maximum sum of 13.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then each test case follows.
The first line of each test case contains a single integer ‘N’ denoting the number of dumbbells in the RACK.
The second line of each test case contains ‘N’ single space-separated integers, denoting the weights of the dumbbells.
Output Format :
For each test case, print the maximum weight Ninja can lift to impress his trainer as per given conditions.
Output for each test case will be printed in a new line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 1000
1 <= RACK[i] <= 10^5
Time Limit: 1 sec
Approaches
It is clear from the given conditions that we need to compute the maximum increasing dumbbells weights sum formed in the given ‘RACK’.
Formally for each index ‘i’ in the given array/list, we calculate the result by letting ‘RACK[i]’ as the last element of the array. So the maximum sum contributed by ‘RACK[i]’ is the sum of ‘RACK[i]’ and the result by ‘RACK[i-1]’.
Basically, we are computing the maximum sum of increasing weights by ‘RACK[i]’ as the last element of the array. Initialize a global variable ‘answer’ which will be our final output as ‘INT_MIN’. We will call our helper function ‘maxIncreasingDumbbellsSumUtil’ which will return the maximum sum of increasing weights. In each recursive call, we will initialize ‘currWeight’ as ‘RACK[N - 1]’.
The algorithm will be-:
- If ‘N = 1’ then return ‘RACK[N - 1]’
- For finding out the sum of the longest increasing sequence ending at ‘i’, we will call a recursive ‘maxIncreasingDumbbellsSumUtil’. Keeping the current index, we will iterate through each element starting from index ‘i=1’. For each ‘i’ do the following :
- If ‘N = 0’ return 0.
- If (RACK[i - 1] >= RACK[N - 1]) we include RACK[N - 1] in our result and recur again then finally update the ‘currWeight’.
- Finally, we update ‘totalWeight’ and return ‘currWeight’.
In the previous approach, we are solving the problem by solving its subproblems and then combining their solutions. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. So, in this approach, we will eliminate the need for solving the same subproblems again and again by using memoization.
Algorithm:
The algorithm is similar to the previous approach with some additions.
We create a ‘lookUp’ array of size ‘N’ where ‘N’ denotes the number of dumbbells in the ‘RACK’. ‘lookUp’ stores the solutions to the subproblems where ‘lookUp[i]’ denotes the maximum sum of increasing subsequence ending at ‘i’. We initialize the ‘lookUp’ by -1. The algorithm will be the same as our previous algorithm with the following additions:
- If ‘N = 1’ return ‘RACK[N - 1]’
- If ‘lookUp[N - 1] != -1’ that means we have already calculated the maximum increasing sum ending at ‘N - 1’ so we simply return ‘lookUp[N - 1]’
- For finding out the sum of the longest increasing sequence ending at ‘i’, we will call a recursive ‘maxIncreasingDumbbellsSum’ keeping the current index, we will iterate through each element starting from index ‘i = 1’. For each ‘i’ do the following :
- If( ‘RACK[i - 1]' >= ‘RACK[N - 1]’ ) we include ‘RACK[N - 1]’ in our result and recur for remaining array.
- Finally, we update ‘lookup’ and return ‘lookUp[N - 1]’.
In this approach for each index ‘i’ as the last element of the subsequence, we iterate through index 0 to i and calculate the result, and update our ‘totalWeight’.
The algorithm will be-:
- We initialize a variable ‘totalWeight = INT_MIN’
- We make a ‘dp’ array of size ‘N’ and initialize it with ‘INT_MIN’. ‘dp[i]’ denotes the maximum sum subsequence ending at ‘RACK[i]’
- Iterate through each element from ‘i’ = 0 to ‘i’ < ‘N’ and for each ‘i’ as the last element of the subsequence do the following -:
- Iterate through each element from ‘j’ = 0 to ‘j’ < ‘i’.
- If ‘RACK[j]’ < ‘RACK[i]’ and ‘dp[i] < dp[j] + RACK[i]’ then update ‘dp[i]’.
- For each ‘i’ update the ‘totalWeight’.
- Finally, we return ‘totalWeight’ as our answer.
Similar problems