The owner of a construction company has a surplus of rods of arbitrary lengths. A local contractor offers
to buy any of the surplus, as long as all the rods have the same exact integer length, referred to as saleLength.
The number of sellable rods can be increased by cutting each rod zero or more times, but each cut has a cost denoted by costPerCut.
After all cuts have been made, any leftover rods having a length other than saleLength must be discarded for no profit.
The owner's total profit for the sale is calculated as:
totalProfit = totalUniFormRods * saleLength * salePrice - totalCuts * costPerCut
where totalUniformRods is the number of sellable rods, salePrice is the per unit
length price that the contractor agrees to pay, and the totalCuts is the total number of times the rods needed to be cut.
Function Description
Complete the function maxProfit in the editor.
maxProfit has the following parameter(s):
costPerCut: cost to make a cut salePrice : per unit length sales pricelengths[n]: integer rod lengthsReturns
int: maximum possible profitExample 1:
Input: lengths = [30, 59, 110], costPerCut = 1, salePrice = 10
Output: 1913
Explanation:Working through the first stanza, length = 30, it is the same length as the first rod, so no cuts are required and there is 1 piece. For the second rod, cut and discard the excess 29 unit rod. No more cuts are necessary and another 1 piece is left to sell. Cut 20 units off the 110 unit rod to discard leaving 90 units, then make two more cuts to have 3 more pieces to sell. Finally sell 5 totalUniformRods, costPerCut = 1 per cut, or 4. Total revenue = 1500 - 4 = 1496. The maximum revenue among these tests is obtained at length 5 for 1913.
Example 2:
Input: lengths = [26, 103, 59], costPerCut = 100, salePrice = 10
Output: 1230
Explanation:Since costPerCut = 100, cuts are expensive and must be minimal. The optimal rod length for maximizing profit is 51, and the rods are cut as shown: lengths[0] = 26: Discard this rod entirely. lengths[1] = 103: Cut off a piece of length 1 and discard it, resulting in a rod of length 102. Then, cut this rod into 2 pieces of length 51. lengths[2] = 59: Cut off a piece of length 8 and discard it, resulting in a rod of length 51. After performing totalCuts = (0) + (1 + 1) + (1) = 3 cuts, there are totalUniformRods = 0 + 2 + 1 = 3 pieces of length saleLength = 51 that can be sold at salePrice = 10 each. This yields a total profit of salePrice * totalUniformRods * saleLength - totalCuts * costPerCut = 10 * 3 * 51 - 3 * 100 = 1230.
1 <= n <= 501 <= lengths[i] <= 1041 <= salePrice, costPerCut <= 100
input:
output: