Question

You are working for a small stock investment company that wants to look for patterns in optimal trading days in a given time period of n days. They want to find the best pair of days in a period of n days to buy a stock on the first day of the pair and sell it on the second day of the pair. That is, they want the biggest positive difference between the selling price on the second day and the buying price on the first day. Assume for simplicity that the buying and selling price on a given day are the same. Assume you know the stock price for every day. The data is given to you in a list sorted by date, earliest day first. You may assume that there exists at least one trade that results in a profit. Specify an O(n log n) Divide and Conquer algorithm. (Note: there are O (n) algorithms that solve this problem but that is not what is asked for here)

Answer 1

We need to find 2 date indexes (left and right) between which profit is maximum.

In divide and conquer approach,

1.we need to divide problem in two parts i.e left half and right half.

the final result will be in one of the three possiblities i.e

1. Left half of the array ( both buy and sell date in left half of the array).

2. Right half of the array ( both buy and sell date in right half of the array).

3. across both side (Buy date in the left half and sell date in right half of the array).

2. Solve the all three and return the maximum among them.

3. Left half and right half of the array will be solved recursively

4. keep track of profit and date indexes.

Algo-

maxprofit (prices, start, end){

mid = start + (end-start)/2;

left_ans= maxProfit(prices,start,mid)

right_ans= maxProfit(prices,mid+1,end)

minLeftIndex = getMinIndex(prices, start, mid) which returns minimum value index in array.

maxRightIndex = getMaxIndex(prices, mid, end) which returns maximum value index in array.

crossProfit = prices[maxRightIndex] - prices[minLeftIndex];

   if(crossProfit>left_ans.profit && crossProfit>right_ans.profit)

              return new ans(crossProfit,minLeftIndex,maxRightIndex);

    else if(left_ans.profit>crossProfit && right_ans.profit>crossProfit)

             return left_ans

     else

            return right_ans

}

feel free to ask any doubt in comments