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

Problem of the day

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.

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

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

```
2
5
1 7 3 9 9
8
3 5 8 9 10 17 17 20
```

```
22
24
```

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

```
1
6
3 5 6 7 10 12
```

```
18
```