Problem title
Difficulty
Avg time to solve

Prime And Validity
Hard
30 mins
Animals And Monsters
Hard
45 mins
Virus Detection
Moderate
--
LCA - Lowest Common Ancestor
Hard
40 mins
Maximize the Gold
Moderate
--
Rotate the Box
Moderate
20 mins
Max K Value
Moderate
10 mins
The Greedy Jeweller
Hard
50 mins
Maximum Difference
Hard
40 mins
Paint House IIl
Hard
--

# Maximum profit

Difficulty: MEDIUM
Avg. time to solve
40 min
Success Rate
75%

Problem Statement

#### Ninja is a poor but an intelligent boy. He has a rod of length ‘N’ units. He wants to earn maximum money by selling this rod in the market. So he cuts the rod into different sizes and each size has a cost associated with it. Determine the maximum money he can earn by cutting the rod and selling its pieces.

##### Note:
``````1. The sizes will range from 1 to ‘N’ and will be integers.

2. The sum of the pieces cut should be equal to ‘N’.

3. Consider 1-based indexing.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The next 2 * T lines represent the ‘T’ test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the rod.

The second line of each test case contains a vector ’A’, of size ‘N’ representing the cost of different lengths, where each index of the array is the sub-length and the element at that index is the cost for that sub-length.
``````

#### Note:

``````Since 1-based indexing is considered, the 0th index of the vector will represent sub-length 1 of the rod. Hence the (N - 1)th index would represent the cost for the length ‘N’.
``````
##### Output Format
``````For each test case, print a single line that contains a single integer which is the maximum cost obtained by selling the pieces.

The output of each test case will be printed in a separate line.
``````

#### Note:

``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints:
``````1 <= T <= 50
1 <= N <= 100
1 <= A[i] <= 100

Where ‘T’ is the total number of test cases, ‘N’ denotes the length of the rod, and A[i] is the cost of sub-length.

Time limit: 1 sec.
``````
##### Sample Input 1:
``````2
5
1 7 3 9 9
8
3 5 8 9 10 17 17 20
``````
##### Sample Output 1:
``````22
24
``````
##### Explanation of sample input 1:
``````In the first test case, the length of rod is 5. Ninja will cut the rod into three pieces one of length 1 and two of the length 2. So total money earned is equal to 1 + 2 * 7 = 15.

In the second test case, the length of rod is 8. Ninja will cut the rod into 8 pieces each of length 1. So the total money earned is 8 * 3 = 24.
``````
##### Sample Input 2:
``````1
6
3 5 6 7 10 12
``````
##### Sample Output 2:
``````18
``````
Console