Maximum Sum Increasing Subsequence

Posted: 28 Jan, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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’.
Try Problem