Hindsight is $\frac{20}{20}$ when it comes to investing in Pokemon cards. Suppose you're given CARDDNC$(P[1,$dots,$n])$:

$/$ your code here

Give a brief verbal explanation for why your algorithm works, and why it runs

in time $O(nlogn).($Yes$,$ there is a faster way of doing this problem.$)$

an array $P[1,$dots,$n],$ where $P[i]$ is the price of a certain card on day $i.$ The goal is to

find the best days to buy and sell in order to maximize your profit. The return value

of your algorithms should be the profit made, i$.$e$.,$ the difference between the selling

price and the buying price.

You may assume that you're only buying and selling one card, the price doesn't change

during a given day, and that the card needs to be bought before it is sold. In other

words, you are trying to maximize $P[j]-P[i]$ over all pairs of indices i and $j,$ where

$ij.$ For example, if the array of prices is

$2,4,3,5,1$

the maximum profit is $3,$ which is achieved when you buy on day $1$ and sell on day $4.$

You can't make a profit of $4$ because $1$ comes after $5.$

For both parts below, write down an algorithm in pseudocode.

$($a$)$ Design a brute force algorithm for solving this problem. Your algorithm should

be of the form:

CARDBRUTE$(P[1,$dots,$n])$:

$//$ your code here

In terms of big$-$O notation, how long does your algorithm take?

$($b$)$ Use divide and conquer to design an algorithm that runs in time $O(nlogn)$

$($Hint: see the maximum subarray problem from class$).$ Your algorithm should be

of the form: