Be the first user to complete this post

  • 0
 Add to List
Medium

552. Stock Single Sell Problem - Divide and Conquer

Objec­tiveGiven an array represents the cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algorithm to maximize the profit in a single buy and sell.

Exam­ple:

 int[] prices = {200, 500, 1000, 700, 30, 400, 900, 400, 50};
Output: Maximum Profit: 870, buy date index: 4, sell date index: 6

Earlier we have seen the Dynamic programming solution, In this post we will discuss the divide and conquer approach

Divide and Conquer

  • The approach is quite similar to “Maximum Subarray Problem – Divide and Conquer”
  • Task is to find out the subarray which has the largest sum. So we need to find out the 2 date indexes (left index and right index) between which the profit is maximum.
  • Divide the problem into 2 parts, the left half and the right half.
  • Now we can conclude the final result will be in one of the three possibilities.
    1. The left half of the array. (Buy date index and sell date index both are in the left half of the array).
    2. The right half of the array. (Buy date index and sell date index both are in the right half of the array).
    3. The result will cross the middle of the array. (Buy date index in the left half of the array and sell date index in the right half of the array).
  • Solve all three and return the maximum among them.
  • The left half and right half of the array will be solved recursively.
  • Maintain an object to keep track of profit and date indexes.

Time Complexity: O(nlogn)

Maximum Profit(Divide & Conquer): 870, buy date index: 4, sell date index: 6

 

Related Problems: