15 pts Stock price changes everyday and the change can be ei

(15 pts) Stock price changes everyday, and the change can be either positive or negative, which corresponds to increase or decrease in its price. Given the stock price difference data of corporation EXPO during a certain period, determine the maximum possible profit that one can gain during this period. You are given an array p1, p2, pa,... pnl where pi is a real number representing the price change on day i and n is the number of days during which the price is monitored. For example, pi 0 means the stock prices increased by pi on day i and pi 0 means the stock price decreased by Ipil on day j. pk 0 means the price stays the same on day k. You are only allowed to buy and sell once in the given period (buy first then sell). Buying and selling on the same day is allowed and your profit will simply be the price difference of that day. (a) (10 pts) Give a dynamic programming algorithm which outputs the maximum profit one can gain by investing in EXPO during the given period. The algorithm should work in O(n) time.

Solution

#include<bits/stdc++.h>

using namespace std;

struct buysell

{

int buy;

int sell;

};

void stockBuySell(int price[], int n)

{

if (n == 1)

return;

int count = 0;

buysell sol[n/2 + 1];

int i = 0;

while (i < n-1)

{

while ((i < n-1) && (price[i+1] <= price[i]))

i++;

if (i == n-1)

break;

sol[count].buy = i++;

while ((i < n) && (price[i] >= price[i-1]))

i++;

sol[count].sell = i-1;

count++;

}

if (count == 0)

cout<<\"There is no day when buying the stock will make profit\";

else

{

for (int i = 0; i < count; i++)

cout<<\"Buy on day: \"<<sol[i].buy<< \" Sell on day: \"<<sol[i].sell;

}

return;

}

int main()

{

int n;

cout<<\"Enter the days\";

cin>>n;

cout<<\"Enter the stock price of a days\";

int i,P[n];

for(i=0;i<n;i++)

{

cin>>P[i];

}

stockBuySell(P, n);

return 0;

}

THIS WILL take O(n) time