 New update is available. Click here to update.

# Maximum Sum Increasing Subsequence

Last Updated: 28 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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’.