Consider plotting the points (yi,xi) on the plane. For each point i we add, we wish to know what is the point j, along with which the point i makes the maximum slope line when the two points are joined. Note that this point lies on the convex segment of the points p0…p(i-1). Thus we keep a convex segment of the points on a stack as we proceed. When we encounter the point i, we keep popping points from the stack till the current point does not form a concave segment with the last two
points on the stack. The last point on the stack is the optimal j we were looking for. Push i on the stack, and proceed. Since each point is pushed/popped at most once, we have a linear time algorithm.