Need help turning the following logic/pseudocode into actual java code, professor wants us to use the algorithm in the pseudocode to get the solution.

1.2 Your goal Your goal is to find a recursion-based computational strategy, whose overall time cost is O(n log n). Below is one algorithmic idea for solving this problem using binary recursions. Its time cost is O(n log n), where n is the input data set size.

An efficient solution. Let p[0..n 1] be the array that stores the stock prices over the n days. Let mid = [n/2]. Say the best trade is to buy the stock on day in and sell the stock on day out, such that the profit from this trade p[out] p[in] is the highest profit one can make from this stock over these n days. Depending on the values of the array elements in p, the values of in and out can fall into one of the following three cases:

Case 1: in mid and out mid, i.e., in the best trade, both buying and selling the stock happen during the first half of the n days. An important observation: If in and out fall into this case, it is certain (in, out) is also the best trade if the stock is on the market only over the days from 0 through mid.

Case 2: in > mid and out > mid, i.e., in the best trade, both buying and selling the stock happen during the second half of the n days. An important observation: If in and out fall into this case, it is certain (in, out) is also the best trade if the stock is on the market only over the days from mid + 1 through n 1.

Case 3: in mid and out > mid, i.e. in the best trade, buying happens in the first half of the n days while the selling happens in the second half of the n days. An important observation: If in and out fall into this case, it is certain: 1) in is the index of the smallest number among p[0..mid], the first half of the array p. 2) out is the index of the largest number among p[mid + 1..n 1], the second half of the array p.

Using the three cases and their observations, we get the recursion-based strategy for finding the best trade:

The condition for recursion exit is when the working subarray has size 1. 2

We recursively find the best trade from p[0..mid], named as Candidate 1. We recursively find the best trade from p[mid + 1..n 1], named as Candidate 2.

We find Candidate 3, where in is the index of the smallest number among p[0..mid] and out is the index of the largest number among p[mid + 1..n 1].

We compare the three candidates and pick/return the one that gives the highest profit.

Below shows the pseudocode of the above strategy, whose time cost is O(n log n). The initial call is: BestTrading(p,0,n-1).

BestTrading(p, low, high){

if(low > high) Throw something is wrong; Exit;

if(low == high) return (low, high, 0); //buy day = sell day = low = high; profit = 0;

mid = floor((low+high)/2);

(left_buy, left_sell, left_profit) = BestTrading(p, low, mid); //candidate 1

(right_buy, right_sell, right_profit) = BestTrading(p, mid+1, high);//candidate 2

(across_buy, across_sell, across_profit) = BestTradingAcross(p, low, high); //candidate 3

if(left_profit >= right_profit && left_profit >= across_profit)

return (left_buy, left_sell, left_profit);

else if(right_profit >= left_profit && right_profit >= across_profit)

return (right_buy, right_sell, right_profit);

else

return (across_buy, across_sell, across_profit);

}

BestTradingAcross(p, low, high){

if(low >= high) Throw something is wrong; Exit;

mid = floor((low+high)/2);

Let x be the index of the location of the smallest number among p[low..mid];

Let y be the index of the location of the largest number among p[mid+1..high];

return (x, y, p[y]-p[x]);

}