Redirecting to
NADOS

Buy And Sell Stocks - One Transaction Allowed

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a number n, representing the number of days.
2. You are given n numbers, where ith number represents price of stock on ith day.
3. You are required to print the maximum profit you can make if you are allowed a single transaction.
Input Format 
A number n
.. n more elements
Output Format 
A number representing the maximum profit you can make if you are allowed a single transaction.
Question Video
Constraints 
0 <= n <= 20
0 <= n1, n2, .. <= 10
Sample Input 
9
11
6
7
19
4
1
6
18
4
Sample Output 
17


  • Editorial

    One transaction => Buy and sell only once

    To get the maximum profit we should buy at minimum price and sell at the maximum price and buy date is before the selling date.

    Let profit_i be the maximum profit that can be earned by selling on the ith day and can be evaluated as follows.

    profit_i = ( price_i ) - ( minimum_price till ith day )

    Finally the required maximum profit will be the maximum value of the profit_i where i is all the valid days.

    Example:

    Given the prices array where index represent the day number and the value represent the price on that day

    prices = { 11, 6, 7, 19, 4, 1, 6, 18, 4 }

    Thus the maximum profit is 17 

    int buy_and_sell_one_trnx(int n, vector
     &prices)
                                {
                                    int min_price = INT_MAX; //To store minimum price found so far
                                    int max_profit = 0;      //To store the overall maximum profit
                                    for (int curr_price : prices)
                                    {
                                        if (curr_price < min_price)
                                            min_price = curr_price;
                                        //curr profit is the max profit that
                                        // can be earned by selling it on curr_price
                                        int curr_profit = curr_price - min_price;
                                        if (curr_profit > max_profit)
                                            max_profit = curr_profit;
                                    }
                                    return max_profit;
                                }

    java false

    Time complexity:

    As we have traversed through prices array only once

    Time complexity = O( n ).

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name