Last Updated: 14 Jan, 2021
Best Time to Buy and Sell Stock III
Hard
Asked in companies
Given an array "prices". In "prices" the ith element is the price of the stock on the ith day. Your task is to find maximum profit at the end of the ith day. You may complete at max 2 transactions.
You can perform a transition with these conditions -
1. Not allowed to engage in more than 1 transaction at a time, which means if you have bought stock then you can buy another stock before selling the first stock.
2. If you bought a stock at ‘X’ price and sold it at ‘Y’ price then the profits ‘Y - X’.
Note:
It is not compulsory to perform an exact '2' transaction.
Input format:
The first line of input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains a single integer 'N', 'N' denotes the length of array ‘prices’.
The second line of each test case contains an 'N' space-separated integers, in which every integer denotes an element of the array "prices".
Output Format
For each test case, you need to print the maximum profit made by selling the stocks.
Note :
You do not need to print anything; it has already been taken care of.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
0 <= A[i] <= 10^9
Time limit: 1 second
Approaches
The basic idea is that, try all possible transactions, means move to every index and try to perform one transaction before the current index and one after the current index. For all the possibilities choose maximum.
- ‘ans = 0’, to store answers as maximum profit.
- Iterate a loop ‘i’ from ‘0’ to ‘n - 2’.
- For every ‘i’, find the best transaction on the left side of right, which means iterate a loop ‘j’ from ‘0’ to ‘i’.
- ‘best transaction on left side = current value - minimum so far’.
- For every ‘i’, find the best transaction on the right side of the right, which means iterate a loop ‘j’ from ‘i + 1’ to ‘n - 1’.
- ‘best transaction on right side = current value - minimum so far’.
- If ‘(best transaction on left side ) + (best transaction on right side) > ans’,
- Update ‘ans= (best transaction on left side ) + (best transaction on right side)’.
- In the end, return ‘ans’.
The basic idea is that, create two “frontArr” and “backArr”. In “frontArr[i]”, we store if we sold a stock at ‘ith’ day or before ‘ith’ day then what will be the maximum profit. In ‘backArr[i]’, we store if we buy and sell a stock after ‘ith’ day then what will be the maximum profit. Then for every ‘i’ check the maximum value of "frontArr[i] + backArr[i + 1]".
- Create a “frontArr” and in “frontArr[i]” store the difference of minimum and maximum value till ‘i’.
- Create a "backArr" and in "backArr[i]" store the difference of minimum and maximum value till ‘i’, so iterate a loop from ‘n - 1’ to ‘0’ in reverse order.
- Use an ‘ans = 0’ to store the answer to return the maximum profit.
- Iterate a loop from ‘0’ to ‘n - 2’.
- If ‘frontArr[i] + backArr[i + 1] > ans’, then update ‘ans = frontArr[i] + backArr[i + 1]’.
- In the end, return ‘ans’.
Similar problems