Best Time to Buy and Sell
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

Question

Best Time to Buy and Sell

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

Accepted Answer

Initially I used many techniques but was not able to get satisfactory results. Then I used the dynamic programming approach to solve this.

Accepted Answer

Recursive Approach

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).
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.
Return MAX.

Space Complexity: O(1)Explanation:

O(N), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, we will only be using the space required for the recursive stack to build.

Time Complexity: O(n^n)Explanation:

O(N^N), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, the recursive function is called N^N times for every element in the array thus the time complexity here becomes O(N^N).

Accepted Answer

Memoization Approach

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],
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.
If MAXPROFIT > MAX, MAX = MAXPROFIT.
Store the results in DP array, DP[START] = MAX, return MAX.

Space Complexity: O(n)Explanation:

O(N), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, we will be memoizing results for N days using O(N) extra space.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, for each day we will only try to sell on the remaining left days one by one. and the results for the remaining days will be stored in our DP array.

Accepted Answer

Peaks and Troughs

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.

Space Complexity: O(1)Explanation:

O(1),

In the worst case, we will only be using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, we will only be iterating on each price once.

Accepted Answer

Positive Slopes Contribution

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.

Space Complexity: O(1)Explanation:

O(1),

In the worst case, we will only be using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where N is the number of the days for which prices are given i.e the size of the input array.

In the worst case, we will only be iterating on each price once.

Note:

Input Format:

Output Format:

Note:

Constraints:

Top UnitedHealth Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern