Reddit is the only major site I know which is regularly (well not so often, but often enough for me to realize) unplanned, and planned, downtime. Makes me wonder whether their architecture is really something to follow.
Just to be sure, "path" must be understood as "trajectory" here? If the hiker doesn't know the starting position then it cannot be "path" as in "line between point A and point B" since there is no point A or B.
So the solution would be something like: "go ahead 10 meters, then turn 45° right, then go ahead 50 meters, then take a Bézier curve left with such parameters, etc"
> The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest.
Again, just to be sure, the "worst-case distance to travel" is the longest distance achieved by the "trajectory" when you apply it starting from any point of the forest?
So basically (assuming you walk at constant speed):
1. Determine a trajectory to follow that guaranties that you would get out of the forest under N seconds (easy).
2. What is smallest possible N and the associated trajectory under which #1 is true? (hard)
Why n/2? If the array is, for example, sorted in the reverse order, then there is no monotonous run at all, in which case I believe the algorithm considers each element from the array being a run in itself, giving n runs.