New update is available. Click here to update.

Last Updated: 28 Jan, 2021

Difficulty: Moderate

```
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.
```

```
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.
```

```
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.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 5
1 <= N <= 1000
1 <= RACK[i] <= 10^5
Time Limit: 1 sec
```

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

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

- If
- 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 ‘keeping the current index, we will iterate through each element starting from index**maxIncreasingDumbbellsSum’***‘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*.*

- If
- 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]’.*

- Iterate through each element from
- For each
*‘i’*update the*‘totalWeight’.* - Finally, we return
*‘totalWeight’*as our answer.

SIMILAR PROBLEMS

Randomly Sorted

Posted: 13 Nov, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Ninja And The Strictly Increasing Array

Posted: 27 Nov, 2022

Difficulty: Moderate

Negative To The End

Posted: 16 Dec, 2022

Difficulty: Easy

8-Queen Problem

Posted: 19 Dec, 2022

Difficulty: Easy

Popular Interview Problems: