Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Stock Single Sell Problem — O(n) Solution

Objec­tive:  Given an array rep­re­sents cost of a stock on each day. You are allowed to buy and sell the stock only once. Write an algo­rithm to max­i­mize the profit in sin­gle 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. Tak­ing one ele­ment at a time, con­sider outer loop value as buy­ing  date index and com­pare it with the every ele­ment in the inner loop which will be con­sid­ered as sell­ing index date. Keep track of the max­i­mum. This will be the max­i­mum profit.

Time Com­plex­ity: O(n^2)

Code:

Approach 2: Divide and Conquer

1.     The approach is quite sim­i­lar to “Max­i­mum Sub­ar­ray Prob­lem – Divide and Con­quer

2.     Task is to find out sub­ar­ray 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 prob­lem into 2 parts, left half and right half.

  1. Now we can con­clude the final result will be in one of the three possibilities.
    1. Left half of the array. (Buy date index and sell date index both are in left half of the array).
    2. Right half of the array. (Buy date index and sell date index both are in right half of the array).
    3. Result will cross the mid­dle of the array. (Buy date index in the and left half of the array and sell date index in right half of the array).
  2. Solve the all three and return the max­i­mum among them.
  3. Left half and right half of the array will be solved recursively.
  4. Main­tain an object to keep track of profit and date indexes.

Time Com­plex­ity: O(nlogn)

Code:


Approach 3: Dynamic Programming

  1. Iter­ate through last date index to start date index.
  2. Keep track of the max­i­mum stock price seen dur­ing iter­a­tion, 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 cur­rent day can be con­sid­ered as buy­ing date so cal­cu­late the dif­fer­ence and com­pare it with the current_profit, if current_profit is less update it with the new value.
  4. After the iter­a­tion, return current_profit.
  5. See the code for more understanding.

Time Com­plex­ity: O(n)

Code:

Out­put:

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

You may also like...