Problem

Submissions

Solution

New

Discuss

27

Difficulty: MEDIUM

Avg. time to solve

40 min

Success Rate

75%

Problem Statement

Suggest Edit

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

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

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

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

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

```
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
2 5 7 8 10
8
3 5 8 9 10 17 17 20
```

```
12
24
```

```
Test case 1:
All possible partitions are:
1,1,1,1,1 max_cost=(2+2+2+2+2)=10
1,1,1,2 max_cost=(2+2+2+5)=11
1,1,3 max_cost=(2+2+7)=11
1,4 max_cost=(2+8)=10
5 max_cost=(10)=10
2,3 max_cost=(5+7)=12
1,2,2 max _cost=(1+5+5)=12
Clearly, if we cut the rod into lengths 1,2,2, or 2,3, we get the maximum cost which is 12.
Test case 2:
Possible partitions are:
1,1,1,1,1,1,1,1 max_cost=(3+3+3+3+3+3+3+3)=24
1,1,1,1,1,1,2 max_cost=(3+3+3+3+3+3+5)=23
1,1,1,1,2,2 max_cost=(3+3+3+3+5+5)=22
and so on….
If we cut the rod into 8 pieces of length 1, for each piece 3 adds up to the cost. Hence for 8 pieces, we get 8*3 = 24.
```

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

```
18
```

Console