This is a C++ Program that Solves the Stock Market Problem using Dynamic Programming technique.
Given the price of share on n days, find the maximum profit that you can make by buying and selling a share at most twice.
In this problem, we are required to find the maximum obtainablem profit with the constraint of buying and selling at most twice. First, we will find the required values with the constraint of 1. Then, using these values we can easily find the results for the constaint of two.
Case-1:
price[]=8, 10, 5, 30, 25, 35 Maximum profit that could be made by buying and selling a share at most twice=35 (by buying on third day and selling on fourth day and then buying on fifth day and selling on sixth day
Here is source code of the C++ Program to Solve the Stock Market Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
#include<bits/stdc++.h>
using namespace std;
int maxProfit(int n, vector<int> &a)
{
int i;
int mx;
int mn;
int profit;
vector<vector<int> >dp(2,vector<int>(n));
//dp[0][i]=maximum profit by buying and selling a stock just once a day by using only values a[0...i]
//dp[1][i]=maximum profit by buying and selling a stock just once a day by using only values a[i...n-1]
//i is the value at which stock will be sold
dp[0][0]=0;
mn=a[0];
for(i=1;i<n;i++)
{
dp[0][i]=max(dp[0][i-1],a[i]-mn);
if(a[i]<mn)
{
mn=a[i];
}
}
//i is the value at which stock will be purchased
dp[1][n-1]=0;
mx=a[n-1];
profit=dp[0][n-1];
for(i=n-2;i>=2;i--)
{
dp[1][i]=max(dp[1][i+1],mx-a[i]);
profit=max(profit,dp[1][i]+dp[0][i-1]);
if(a[i]>mx)
{
mx=a[i];
}
}
return profit;
}
int main()
{
int i,n;
cout<<"Enter the number of stock values ";
cin>>n;
vector<int> a(n);
cout<<"Enter the values of stock on each day "<<endl;
for(i=0;i<n;i++)
cin>>a[i];
cout<<"Maximum profit that could be made by buying and selling a share at most twice"<<endl;
cout<<maxProfit(n,a);
cout<<endl;
return 0;
}
The main function takes input for the stock values. Then, these values are passed to the function maxProfit as parameters. In the maxProfit function, we created a matrix to memoize values. The final result is returned by this function which is displayed by the standard output.
Case-1: $ g++ stock_profit.cpp $ ./a.out Enter the number of stock values 6 Enter the values of stock on each day 8 10 5 30 25 35 Maximum profit that could be made by buying and selling a share at most twice 35
Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.
- Practice Programming MCQs
- Practice Design & Analysis of Algorithms MCQ
- Apply for Computer Science Internship
- Check Computer Science Books
- Check Programming Books