Stock Market Problem – Dynamic Programming Solutions

«
»

This is a C++ Program that Solves the Stock Market Problem using Dynamic Programming technique.

Problem Description

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.

Problem Solution

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.

advertisement
Expected Input and Output

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
Program/Source Code

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.

advertisement
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int maxProfit(int n, vector<int> &a)
  6. {
  7.     int i;
  8.     int mx;
  9.     int mn;
  10.     int profit;
  11.  
  12.     vector<vector<int> >dp(2,vector<int>(n));
  13.  
  14.     //dp[0][i]=maximum profit by buying and selling a stock just once a day by using only values a[0...i]
  15.     //dp[1][i]=maximum profit by buying and selling a stock just once a day by using only values a[i...n-1]
  16.  
  17.     //i is the value at which stock will be sold
  18.     dp[0][0]=0;
  19.     mn=a[0];
  20.  
  21.     for(i=1;i<n;i++)
  22.     {
  23.         dp[0][i]=max(dp[0][i-1],a[i]-mn);
  24.  
  25.         if(a[i]<mn)
  26.         {
  27.             mn=a[i];
  28.         }
  29.  
  30.     }
  31.  
  32.     //i is the value at which stock will be purchased
  33.     dp[1][n-1]=0;
  34.     mx=a[n-1];
  35.     profit=dp[0][n-1];
  36.  
  37.     for(i=n-2;i>=2;i--)
  38.     {
  39.         dp[1][i]=max(dp[1][i+1],mx-a[i]);
  40.  
  41.         profit=max(profit,dp[1][i]+dp[0][i-1]);
  42.  
  43.         if(a[i]>mx)
  44.         {
  45.             mx=a[i];
  46.         }
  47.  
  48.     }
  49.  
  50.     return profit;
  51. }
  52.  
  53. int main()
  54. {
  55.     int i,n;
  56.     cout<<"Enter the number of stock values ";
  57.     cin>>n;
  58.  
  59.     vector<int> a(n);
  60.     cout<<"Enter the values of stock on each day "<<endl;
  61.     for(i=0;i<n;i++)
  62.         cin>>a[i];
  63.  
  64.     cout<<"Maximum profit that could be made by buying and selling a share at most twice"<<endl;
  65.     cout<<maxProfit(n,a);
  66.  
  67.     cout<<endl;
  68.     return 0;
  69. }
Program Explanation

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.

Runtime Test Cases
 
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.

advertisement

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!
advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn