Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

# Maximum profit

Moderate
0/80
Average time to solve is 40m
0 upvote

## 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.
``````
Detailed explanation ( Input/output format, Notes, Images )
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