Stock Market Problem using Dynamic Programming

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.

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.

```
 
```
```
#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;
```
```
}
```

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.

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

« Prev - Building Problem – Dynamic Programming Solutions

» Next - Longest Arithmetic Progression – Dynamic Programming Solutions

Related Posts:

Practice Programming MCQs
Practice Design & Analysis of Algorithms MCQ
Apply for Computer Science Internship
Check Computer Science Books
Check Programming Books

Recommended Articles: