(15 pts) Stock price changes everyday, and the change can be either positive or
ID: 3783618 • Letter: #
Question
(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, p3,...,pr] 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 psExplanation / Answer
(a) Let us call the array of prices be A. Start from the start of the array, we construct an array B, which will hold the prefix sum of the array A.
B[i] = P1+P2...Pi for i=1 to n
We construct another array C from array B, which will hold the minimum value of the array B starting from the back of the array.
C[i] = min(B[n],B[n-1]...B[i+1])
Now we iterate all over B:
max = 0
for i = 1:n
temp = B[i]-C[i]
if (temp>max)
max = temp
At the end of the loop we have the maximum profit in the variable max.
(b)
In the second we create D[i] such that
D[i] = j, where C[i] = B[j]
In the loop
max = 0
st=1
end=1
for i = 1:n
temp = B[i]-C[i]
if (temp>max)
max = temp
st=i
end = D[i]
Now the buy and sell dates will be in st and end variables.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.