Last Updated: 4 Sep, 2020
Best Time to Buy and Sell
Moderate
Asked in companies
You are given an array(PRICES) of stock prices for N consecutive days. Your task is to find the maximum profit that you can make by completing as many transactions as you like, where a transaction denotes buying one and selling one share of the stock.
Note:
You must sell the stock before you buy it again.
Input Format:
The first line of input contains an integer value N, denoting the size of the input array.
The second line contains N single space-separated integers, denoting the prices on each day.
Output Format:
The only output line contains an integer, denoting the maximum profit.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints:
1 <= N <= 5 * 10^4
0 <= PRICES[i] <= 10^4
Time Limit: 1sec
Approaches
In this approach, we will be using recursion, where we will have a recursive method let's say MAX_PROFIT(PRICES, START) to find the maximum profit that we can make by doing any number of transactions starting from the START index.
To calculate this we will iterate on our prices starting from PRICES[START] till the last price. We will let the current price as the start of a transaction(buy price) and for each START, we will iterate over the next remaining prices and consider them as the end of the transaction(sell price). Let’s say the sell index ends. So the profit for this transaction is profit is PRICES[END] - PRICES[START]. Let it be equal to CURPROFIT (remember we will only choose that END index having price greater than the price of the START index. ).
Now we will calculate the maximum profit possible for the days after the ending day of the current transaction using recursion. So the PROFIT = CURPROFIT + MAX_PROFIT(PRICES, END + 1) and we will find the maximum of all possible profits.
Algorithm:
int MAX_PROFIT(PRICES, START):
- If there are no prices left to consider, Return.
- Initialize MAX with zero.
- For all prices i.e i from START to the SIZE - 1 index, where size denotes the size of the prices array. Buy the stock(start transaction).
- Initialize MAXPROFIT with zero.
- For remaining prices, j from i + 1 to SIZE - 1, Sell the stock(end transaction) if PRICE[j] > PRICE[i],
- CURPROFIT = PRICE[j] - PRICE[i].
- Calculate the maximum profit for the remaining prices and add to PROFIT, PROFIT += MAX_PROFIT(PRICES, j + 1).
- If PROFIT > MAXPROFIT , MAXPROFIT = PROFIT.
- If MAXPROFIT > MAX, MAX = MAXPROFIT.
- Return MAX.
In this approach, we will be using recursion, where we will have a recursive method let's say MAX_PROFIT(PRICES, START) to find the maximum profit that we can make by doing any number of transactions starting from the START index.
First, we will check whether we have already calculated the results starting from the START index. If calculated, then we will return the results and won’t calculate them again. Otherwise, to calculate this we will iterate on our prices starting from PRICES[START] till the last price. We will let the current price as the start of a transaction(buy price) and for each start, we will iterate over the next remaining prices and consider them as the end of the transaction(sell price). Let’s say the sell index ends. So the profit for this transaction is profit is PRICES[END] - PRICES[START]. Let it be equal to CURPROFIT (remember we will only choose that END index having a price greater than the price of the START index.).
Now we will calculate the maximum profit possible for the days after the ending day of the current transaction using recursion. So the PROFIT = CURPROFIT + MAX_PROFIT(PRICES, END + 1) and we will find the maximum of all possible profits and store these results to be used in future.
Algorithm:
int MAX_PROFIT(PRICES, START, DP):
- If there are no prices left to consider, Return.
- If the result for START is already calculated, Return DP[START].
- Initialize MAX with zero.
- For all PRICES i.e i from START to the SIZE - 1 index, where size denotes the size of the prices array. Buy the stock(start transaction).
- Initialize MAXPROFIT with zero.
- For remaining prices, j from i + 1 to SIZE - 1, Sell the stock(end transaction) if PRICE[j] > PRICE[i],
- CURPROFIT = PRICE[j] - PRICE[i].
- Calculate the maximum profit for the remaining prices and add to profit, PROFIT += MAX_PROFIT(PRICES, j + 1).
- If PROFIT > MAXPROFIT , MAXPROFIT = PROFIT.
- If MAXPROFIT > MAX, MAX = MAXPROFIT.
- Store the results in DP array, DP[START] = MAX, return MAX.
To calculate the maximum profit, we will first plot the graph where the x-axis will denote the indexes and the y-axis will denote the prices. We should buy the stock at the first trough and then sell the stock at the day which is the first peak. In a similar way, the overall profit will be done by doing transactions for each adjacent trough and peak in the graph starting from the first trough and ending at the last peak.
For example, for the given prices [2,4,7,1,3,5] given below is the graph plotted. Transactions will be as follows:
Transaction 1 - Buy at the first trough(price = 2) and sell at first peak(price = 7), making a profit of (7 - 2) = 5
Transaction 2 - Buy at second trough(price = 1) and sell at second peak(price = 5), making a profit of 4
Total profit = 5 + 4 = 9.
To calculate the maximum profit, we will first plot the graph where the x-axis will denote the indexes and the y-axis will denote the prices. Now if you carefully observe the graph and the solution discussed in approach 3. It can be seen that the maximum profit will equal the sum of differences of all the consecutive price pairs where in each pair the price on an ith day is greater than the prices on (i-1)th day. 1 <= i <= N - 1.
Similar problems