Our UBC student from quiz 3 has finished her co-op position at Greedy Bank. Disillusioned by Greedy Bank's predatory debit-reordering schemes, she's moved on to bigger and better things at - you guessed it -a different bank. At DC Bank, overdraft fees are charged over an interval of transactions by multiplying the number of transactions by the minimum amount by which the account is overdrawn over that same period. For example, if Customer A' s account balances were [-20, -50, -70, -10], Customer A would be charged 4 * $10 = $40. If Customer B's account balances were [-20, -40, +10, -10], he would not be charged anything, since at the third transaction his overdraft amount was zero (as he had a positive balance). We can define this mathematically as follows: for an size n array A of account balances, the overdraft fee is f (A) = max {0, -n * max (A [1], A [2], ..., A [n])}. We can also charge overdraft fees for a particular interval of A: starting at index i for an interval of d transactions, the overdraft fee is f (i, d) = max {0, - d * max (A [i], A [i + 1], ..., A [i + d - 1])}. At the end of the month, DC Bank gets each account's list of account balances. They're allowed to charge an overdraft fee for a single interval over the month. What they want is to calculate the best such interval: namely, they want the start index i and number of transactions d such that f (i, d) is maximized. For example, the best overdraft interval is underlined in the following account balance array: [-5, 0, 10, 5, -5, -10, -4, -1, 5]. Using 1-based indexing, the overdraft fee for this optimal interval starting at index 5 and lasting 3 transactions is f (5, 3) = max {0, -3 * max (-5, -15, -4)} = 12. Give a polynomial-time brute force algorithm to solve this problem. Give and briefly justify a good asymptotic bound on the runtime of your algorithm. For simplicity, assume that all positive account balances in A have been replaced by 0. We can now define f (i, d) = -d * max (A [i], A [i + 1], ..., A [i + d]). Suppose the maximum element in A is A [k] = -4, and suppose that A has length n. What's the maximum overdraft fee for all intervals that include A [k]? Briefly justify your answer. Give an efficient algorithm (ideally using the insight from question 1) to find the optimal overdraft interval. Give and briefly justify a good asymptotic bound on the worst- case runtime of your algorithm. Give and briefly justify a good asymptotic bound on the average - case runtime of your algorithm. A segment tree is a data structure that lets you obtain the maximum value of an interval A [i] to A [j], for 1 lessthanorequalto i lessthanorequalto j lessthanorequalto n, in O (log n) time, where n is the length of A. The segment tree takes 0 (n) time to build. Describe how you could modify your algorithm to obtain a better worst - case runtime than you computed in question 3. Our UBC student from quiz 3 has finished her co-op position at Greedy Bank. Disillusioned by Greedy Bank's predatory debit-reordering schemes, she's moved on to bigger and better things at - you guessed it -a different bank. At DC Bank, overdraft fees are charged over an interval of transactions by multiplying the number of transactions by the minimum amount by which the account is overdrawn over that same period. For example, if Customer A' s account balances were [-20, -50, -70, -10], Customer A would be charged 4 * $10 = $40. If Customer B's account balances were [-20, -40, +10, -10], he would not be charged anything, since at the third transaction his overdraft amount was zero (as he had a positive balance). We can define this mathematically as follows: for an size n array A of account balances, the overdraft fee is f (A) = max {0, -n * max (A [1], A [2], ..., A [n])}. We can also charge overdraft fees for a particular interval of A: starting at index i for an interval of d transactions, the overdraft fee is f (i, d) = max {0, - d * max (A [i], A [i + 1], ..., A [i + d - 1])}. At the end of the month, DC Bank gets each account's list of account balances. They're allowed to charge an overdraft fee for a single interval over the month. What they want is to calculate the best such interval: namely, they want the start index i and number of transactions d such that f (i, d) is maximized. For example, the best overdraft interval is underlined in the following account balance array: [-5, 0, 10, 5, -5, -10, -4, -1, 5]. Using 1-based indexing, the overdraft fee for this optimal interval starting at index 5 and lasting 3 transactions is f (5, 3) = max {0, -3 * max (-5, -15, -4)} = 12. Give a polynomial-time brute force algorithm to solve this problem. Give and briefly justify a good asymptotic bound on the runtime of your algorithm. For simplicity, assume that all positive account balances in A have been replaced by 0. We can now define f (i, d) = -d * max (A [i], A [i + 1], ..., A [i + d]). Suppose the maximum element in A is A [k] = -4, and suppose that A has length n. What's the maximum overdraft fee for all intervals that include A [k]? Briefly justify your answer. Give an efficient algorithm (ideally using the insight from question 1) to find the optimal overdraft interval. Give and briefly justify a good asymptotic bound on the worst- case runtime of your algorithm. Give and briefly justify a good asymptotic bound on the average - case runtime of your algorithm. A segment tree is a data structure that lets you obtain the maximum value of an interval A [i] to A [j], for 1 lessthanorequalto i lessthanorequalto j lessthanorequalto n, in O (log n) time, where n is the length of A. The segment tree takes 0 (n) time to build. Describe how you could modify your algorithm to obtain a better worst - case runtime than you computed in question 3