Jack Ostrich, a notorious pirate, has come across a single-file convoy of merchant ships that he would like to plunder. Some of these ships, however, are well defended, and the cost of repairing Jack's ship, the Blue Pearl, after engaging them would amount to more than their treasure is worth. Further complicating measures is the fact that, while Jack can choose any point in the convoy to break off, he cannot return after doing so, and must engage each ship in the convoy up to that point. For example, consider the following convoy:

Then, breaking off the convoy after the second ship would be the best option, as it yields a net profit of 11 (which is the highest possible given this convoy). Assuming that Jack has already calculated the cost or benefit to plundering each merchant ship: (a) Give an 0(n) algorithm that will let him walk away with the maximum net profit. (b) Suppose Jack has hired an expert navigator, and can now choose an interception point as well as a breakoff point. Give an 0(n * log(n)) algorithm that makes the best use of his new ability.

Transcribed Image Text:

40 40 40 40 40 40 40 40 40 4 5 6 -9 2 -8 4 -7 3 -5 8 40 40 40 40 40 40 40 40 40 4 5 6 -9 2 -8 4 -7 3 -5 8

Answer rating: 100% (QA)

a On All arrays are 1 indexed arrn array of profits and losses of each ship First we find the sum of ... View the full answer