o pts) Projessor Dumbledore needs your help optimiang the Hogwarts budget. rou be given an array A of erchange rates for muggle money and wizard coins, erpressed as integers. Your task is help Dumbledore marimize the payoff by buying at some time i and selling at a future time j > i, such that both Aj] Ai] and the corresponding difference of Alj] Ali] is as large as possible For erample, let A [8,9, 3, 4, 14, 12, 15, 19,7, 8, 12, 11]. If we buy stock at time i 2 Name ID SCI 3104, Algorithms roblem Set 1 Profs. Grochow & Layer Spring 2019, CU-Boulder with Ai3 and sell at time 7 with A)19, Hogwarts gets in income of 19-316 coins (a) Consider the pseudocode below that takes as input an array A of size n: makeWizardMoney (A): maxCoinsSoFar0 for i0 to length(A)-1 f for j = i+1 to length (A) { coins = A[j] -ALi] if (coins > maxCoinsSoFar) { maxCoinsSoFar = coins } return maxCoinsSoFar What is the running time complerity of the procedure above? Write your answer as a bound in terms of n (b) Erplain (1-2 sentences) under what conditions on the contents of A the makeWizardMoney algorithm will return 0 coins. (c) Dumbledore knows you know that makeWizardMoney is wildly inefficient. With a wink, he suggests writing a function to make a new array M of size n such that That is, Mi gives the minimum value in the subarray of Al0..i Write pseudocode to compute the array M. What is the running time complerity of your pseudocode? Write your answer as a bound in terms of n