244. Rod Cutting
MediumDynamic Programming
A rod of length n can be cut into pieces; a piece of length i sells for price[i]. Print the maximum revenue.
Input format
Line 1: n Line 2: price[1] … price[n]
Output format
The maximum revenue.
Example 1
Input
8 1 5 8 9 10 17 17 20
Output
22
Example 2
Input
8 3 5 8 9 10 17 17 20
Output
24
Constraints
1 ≤ n ≤ 1000
Read input from standard input and print the answer to standard output. Your code is judged against 4 test cases, most of them hidden.
Loading the MyLoginn IDE…