Our goal is to buy and sell a given stock with maximum prot, assuming (not quite
ID: 3683715 • Letter: O
Question
Our goal is to buy and sell a given stock with maximum prot, assuming (not quite realistically)that we are able to predict the future. To be more specic, we assume we have an array P[1..n] (n 2)such that for each i 1..n, P[i] is the price of the stock on day i; our goal is to compute an array A[1..n]of actions where each action is either None, Buy, or Sell. We require that after removing the Nones, thesequence of actions is of the form Buy,Sell,...Buy,Sell. Also, we require that there is a “cool down” day:a Sell cannot be immediately followed by a Buy.
To solve this problem we shall employ 4 tables, B[1..n] and S[1..n] and C[1..n] and M[1..n], with intendedmeaning given below:
• for i 1..n, B[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = buy (thus B[1] = P[1]);
• for i 1..n, S[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = sell (thus S[1] = 0);
• for i 1..n, C[i] is the maximum prot possible after a sequence of actions A[1]..A[i] whereA[i] = none (thus C[1] = 0);
• for i 1..n, M[i] is the maximum prot possible after a sequence of actions A[1]..A[i] where thereexists j 1..i such that A[j] = buy and A[k] = none for all k j + 1..i (thus M[1] = P[1]).
1. Write, and justify, the recurrences for computing (for i 2..n) the values of B[i] and S[i] andC[i] and M[i], given the values of B[i 1] and S[i 1] and C[i 1] and M[i 1].
2. Using the recurrences from step 1, write a dynamic programming algorithm to ll the arraysB[1..n] and S[1..n] and C[1..n] and M[1..n] (you may assume your language has a Max operator).
3. Augment the algorithm from step 2 so that it computes in A[1..n] an optimal action sequence,and the resulting prot.
4. Analyze the space use, and running time, of the algorithm that was developed in step 2 andaugmented in step 3.
Explanation / Answer
Algorithm:
1) Create a table profit[0..n-1] and initialize all values in it 0.
2) Traverse price[] from right to left and update profit[i] such that profit[i] stores maximum profit achievable from one transaction in subarray price[i..n-1]
3) Traverse price[] from left to right and update profit[i] such that profit[i] stores maximum profit such that profit[i] contains maximum achievable profit from two transactions in subarray price[0..i].
4) Return profit[n-1]
Program Code:
// C++ program to find maximum possible profit with at most
// two transactions
#include<iostream>
using namespace std;
// Returns maximum profit with two transactions on a given
// list of stock prices, price[0..n-1]
int maxProfit(int price[], int n)
{
// Create profit array and initialize it as 0
int *profit = new int[n];
for (int i=0; i<n; i++)
profit[i] = 0;
/* Get the maximum profit with only one transaction
allowed. After this loop, profit[i] contains maximum
profit from price[i..n-1] using at most one trans. */
int max_price = price[n-1];
for (int i=n-2;i>=0;i--)
{
// max_price has maximum of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i] = max(profit[i+1], max_price-price[i]);
}
/* Get the maximum profit with two transactions allowed
After this loop, profit[n-1] contains the result */
int min_price = price[0];
for (int i=1; i<n; i++)
{
// min_price is minimum price in price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e., profit[i-1]
// b) (Buy, Sell) at (min_price, price[i]) and add
// profit of other trans. stored in profit[i]
profit[i] = max(profit[i-1], profit[i] +
(price[i]-min_price) );
}
int result = profit[n-1];
delete [] profit; // To avoid memory leak
return result;
}
// Drive program:
int main()
{
int price[] = {2, 30, 15, 10, 8, 25, 80};
int n = sizeof(price)/sizeof(price[0]);
cout << "Maximum Profit = " << maxProfit(price, n);
return 0;
}
Output:
Time complexity of the above solution is O(n).
// C++ program to find maximum possible profit with at most
// two transactions
#include<iostream>
using namespace std;
// Returns maximum profit with two transactions on a given
// list of stock prices, price[0..n-1]
int maxProfit(int price[], int n)
{
// Create profit array and initialize it as 0
int *profit = new int[n];
for (int i=0; i<n; i++)
profit[i] = 0;
/* Get the maximum profit with only one transaction
allowed. After this loop, profit[i] contains maximum
profit from price[i..n-1] using at most one trans. */
int max_price = price[n-1];
for (int i=n-2;i>=0;i--)
{
// max_price has maximum of price[i..n-1]
if (price[i] > max_price)
max_price = price[i];
// we can get profit[i] by taking maximum of:
// a) previous maximum, i.e., profit[i+1]
// b) profit by buying at price[i] and selling at
// max_price
profit[i] = max(profit[i+1], max_price-price[i]);
}
/* Get the maximum profit with two transactions allowed
After this loop, profit[n-1] contains the result */
int min_price = price[0];
for (int i=1; i<n; i++)
{
// min_price is minimum price in price[0..i]
if (price[i] < min_price)
min_price = price[i];
// Maximum profit is maximum of:
// a) previous maximum, i.e., profit[i-1]
// b) (Buy, Sell) at (min_price, price[i]) and add
// profit of other trans. stored in profit[i]
profit[i] = max(profit[i-1], profit[i] +
(price[i]-min_price) );
}
int result = profit[n-1];
delete [] profit; // To avoid memory leak
return result;
}
// Drive program:
int main()
{
int price[] = {2, 30, 15, 10, 8, 25, 80};
int n = sizeof(price)/sizeof(price[0]);
cout << "Maximum Profit = " << maxProfit(price, n);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.