This post is completed by 2 users

  • 2
 Add to List
Medium

223. Stock Single Sell Problem - Dynamic Programming - O(n)

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

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)

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)

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

Related Problems: