Minimum Battery Limit

You are given M delivery locations located on a linear (or circular) path and D drones. The positions of the delivery locations are given in an array. A single drone can deliver to a consecutive segment of locations provided that the distance between the first and the last location in that segment does not exceed its battery limit L. Find the minimum battery limit L required so that all delivery locations can be covered by at most D drones.

In other words, partition the sorted list of positions into at most D contiguous segments such that if a segment covers locations between indices i and j, then
\(L \geq (\text{positions}[j] - \text{positions}[i])\).
You need to minimize L.

Note: If a segment contains only one delivery location, the required battery limit for that segment is 0.

Example: For M = 3, D = 2 and positions [1, 7, 15], one optimal partition is to assign the first two locations to the first drone (battery requirement = 7 - 1 = 6) and the last location to the second drone (battery requirement = 0). Hence, the minimum battery limit required is 6.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains two space-separated integers: M (the number of delivery locations) and D (the number of drones).
2. The second line contains M space-separated integers representing the positions of the delivery locations.

outputFormat

Output a single integer representing the minimum battery limit required so that all delivery locations can be covered.

The output should be printed to standard output (stdout).

3 2
1 7 15

6