Find max obtainable price by selling pieces of a rod

Given a rod of length ‘targetSize’

Given an array of prices where price at each index is the price obtained by selling rod of length equal to that index.

Find out the max price which can be obtained by selling pieces of that rod.

Solution: This is very similar to the above problem with some important differences.

If we had price available for only one size, then max price obtainable for any ‘targetSize’ is easy. We can create a lookup table (rather a lookup array) which will store the max price obtainable if there were only one price available.

Let maxPrice be that array whose every index will store max price obtainable for target-size equal to that index.

maxPrice[0] = 0 // if target-Size is 0, then we cannot sell it, hence max price is 0

maxPrice[1] = prices[1]; // assuming price[0] is 0 to make calculation easier.

maxPrice[2] = prices[1] + maxPrice[1];

maxPrice[3] = prices[1] + maxPrice[2];

Now, if we had one more price available, then the above maxPrice array will need to have a second pass where the max price obtainable at every target-Size is changed if the introduction of newly added price fetches higher value.

Second pass is as follows:

maxPrice[0] = 0;

maxPrice[1] = prices[1]; // price of size 2 cannot affect max-prices of sizes less than 2

maxPrice[2] = MAX ( maxPrice[2] , prices[2] ) ;

maxPrice[3] = MAX ( maxPrice[3] , prices[2] + maxPrice[1]);

If we now introduce the third price, then fourth and so on, we will need to make that many passes on the above array.

maxPrice[targetSize] will then give us the required answer.

Without dynamic programming, recursive solution for the above would have computed solutions to the same problem again and again as follows:

Note: The above does not consider the case when (targetSize-i) is less than 0. In that case, the recursive call returns 0 which is added to prices[i] in the parent calling function. This is incorrect, since we cannot sell a piece which is larger than the remaining size.

So, if price array was [1, 5, 3, 200] and target-size was 100, above will return 200 even though we cannot sell rod of size 200 in this case.

This can be eliminated by putting in a check for i < targetSize.

Dynamic programming eliminates the repeated recursion by using a table look-up as follows:

(Observe the above check has been put in this implementation)

int findMaxPrice (int prices [], int maxRodSize)
{
    if (maxRodSize <= 0 || prices.length <= 0)
        return 0;

    int maxPriceForSizeK[maxRodSize+1] = {0};

    // outer loop introduces each size/price one by one
    for (int nextSize=1; nextSize <= prices.length; nextSize++)
    {
        // inner loop finds the effect of introduction of each size/price
        // on max-price available till now with previous sizes/prices.
        for (int S=nextSize; S<=maxRodSize; S++)
        {
            if (nextSize > S && maxPriceForSizeK[S-nextSize] > 0)
            {
                maxPriceForSizeK[S] = Math.max (
                    maxPriceForSizeK[S],
                    prices[nextSize] + maxPriceForSizeK[S - nextSize]
                );    
            }
        }
    }

    return maxPriceForSizeK[maxRodSize];
}