This post is completed by 2 users

  • 2
 Add to List
Hard

Stock Single Sell Problem - O(n) Solution

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

Approach 1: Brute Force

Use two nested loops. Taking one element at a time, consider the outer loop value as buying date index and compare it with every element in the inner loop which will be considered as the selling index date. Keep track of the maximum. This will be the maximum profit.

Time Complexity: O(n^2)

Code:


Approach 2: Divide and Conquer

1.     The approach is quite similar to “Maximum Subarray Problem – Divide and Conquer”

2.     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.

3.     Divide the problem into 2 parts, the left half and the right half.

  1. 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).
  2. Solve all three and return the maximum among them.
  3. The left half and right half of the array will be solved recursively.
  4. Maintain an object to keep track of profit and date indexes.

Time Complexity: O(nlogn)

Code:


Approach 3: Dynamic Programming

  1. Iterate through the last date index to the start date index.
  2. Keep track of the maximum stock price seen during iteration, say it is max_sell_price and current_profit.
  3. For any i-th day, there are only two possibilities –
    1. Either price on the i-th day is greater than max_sell_price, in that case, update the max_sell_price with that price.
    2. Else (price on the i-th day is less than max_sell_price) so it means the current day can be considered as buying date so calculate the difference and compare it with the current_profit, if the current_profit is less update it with the new value.
  4. After the iteration, return current_profit.
  5. See the code for more understanding.

Time Complexity: O(n)

Code:


Maximum Profit(DP): 870, buy date index: 4, sell date index: 6

Also Read: