Best Time to Buy and Sell

Posted: 4 Sep, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1

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):

  1. If there are no prices left to consider, Return.
  2. Initialize MAX with zero.
  3. 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).
    1. Initialize MAXPROFIT with zero.
    2. For remaining prices, j from i + 1 to SIZE - 1, Sell the stock(end transaction) if PRICE[j] > PRICE[i],
      1. CURPROFIT = PRICE[j] - PRICE[i].
      2. Calculate the maximum profit for the remaining prices and add to PROFIT, PROFIT += MAX_PROFIT(PRICES, j + 1).
      3. If PROFIT > MAXPROFIT , MAXPROFIT = PROFIT.
    3. If MAXPROFIT > MAX, MAX = MAXPROFIT.
  4. Return MAX.
Try Problem