Given an array A of predicted prices for bitcoin, you are asked to buy bitcoin at some time i and sell it at a future time j > i, such that both A[j] > A[i] and the corresponding profit of A[j] A[i] is as large as possible.

For example, let A = [7,6,1,11,10,13,8,20,19,9,10]. If you buy bitcoin at time i = 2 with A[i] = 1 and sell at time j = 7 with A[j] = 20, you make the maximum profit of 20 1 = 19 megabucks.

(a) Consider the pseudocode below that takes as input an array A of size n:

makeMaxProfit(A) : maxProfitSoFar = 0 

1

CSCI 3104, Algorithms Chen, Hoenigman Assignment 1 - Due Sept. 7 by 5pm Fall 2018, CU-Boulder

 for i = 0 to length(A)-1 { for j = i+1 to length(A) { 

 profit = A[j] - A[i] if (profit > maxProfitSoFar) { maxProfitSoFar = profit } 

 }} return maxProfitSoFar 

Use one or two sentences to explain under what circumstances the algorithm will return a profit of 0.

(b) The algorithm makeMaxProfit is not efficient. You can compute the maximum profit more efficiently by keeping track of the following when scanning from A[0] to A[i]:

TheminimumpricesofarMinPSoFar=min0ji A[j]. Writepseudocode that finds MinPSoFar recursively.

The current profit CurrentProfit = A[i] MinPSoFar if you purchase at the minimum price so far and sell at price A[i].

Write pseudocode that finds the maximum profit so far recursively based on CurrentProfit. Here, the maximum profit so far is the maximum profit that can be obtained if you purchase and sell by time i.

(c) Implement the algorithm outlined in (3b) in Python, and run it using an array of 50 prices. Submit the Python code and report the input array and the maximum profit.