Lets assume you start with one piece of tape from the leftmost to the rightmost broken cabin. When more pieces of tape are allowed, there must be better solutions.

So you want to remove as much tape as possible. The lengths of tape that are candidate for removal are the distances between consecutive broken cabins (BTW: if you think about it, the +1 in length=B-A+1 is irrelevant!).

Given a set of numbers and being allowed to take K of them, how do you maximize the sum? Obviously by picking the K largest numbers. Hence my algorithm is just:

Copy Code

apply the minimal piece of tape spanning the broken cabins while(more pieces are allowed) { remove largest piece of tape linking two neighboring broken cabins }

Two comments:

- when the largest piece is present more than once, it doesn't matter which one you pick (or pick first);

- if the largest gap were to become zero (i.e. adjacent cabins), there is no need to split further.

Example 1:

Copy Code

Input 4 100 2 20 30 75 80

Connect all [20 30 75 80]

Locate largest link, its 30-75, and remove it: [20 30] [75 80]

Example 2:

Copy Code

Input 6 200 3 20 30 75 80 110 140

Connect all [20 30 75 80 110 140]

Locate largest link, its 30-75, and remove it: [20 30] [75 80 110 140]

Locate largest remaining link,its 80-110 or 110-140, and remove it: [20 30] [75 80] [110 140]

or [20 30] [75 80 110] [140]

:)

PS: you can also treat it bottom up: start with N pieces of length 1, one for every broken cabin (and probably more pieces than you are allowed); now add some tape, until the number of tape islands reaches the allowed number. Here, obviously you first apply tape to the shortest distances. The result will be the same.