I was asked this in Microsoft : a variant of the rod-cutting problem.

Given a rod of length 'n' and an array denoting the profits for each length. Please find the locations at which the cuts are to be made for maximum profit.