Carey needs to use the university's GPU servers for her studies. Each semester, the servers are available for n consecutive days, but on each day i$,$ they are only available for h$,$ hours. Also a student cannot connect to the GPUs

tor any two consecutive days. Carey wants to determine the days she should use the GRUs in order to maximize her GPU usage time.

For example, assume that n $=5,$ and hi $=1,$ h$2=9,$ h$3=5,$ ha $=4,$ hs $=7.$ So Carey should use the GPUs on the

$2$nd and $5$th day so that she can use them for $9-$: $7=16$ hours

$($a$)(5$ pts$]$ Provide a counter example to show that the following greedy algorithm does not always return the

correct days.

Initialize a set H to an empty set;

Mark all days as valid;

while there are some valid days do

choose a valid day i with maximum hi; add he to H;

if i is not the first day, mark i $-1$ as invalid;

L if i is not the last day, mark i $+1$ as invalid; return H;

$($b$)(10$ pts$]$ Provide a dynamic programming algorithm to solve the problem. The time complexity for your algorithm should be independent of his and must be polynomial in n$.$

$($c$)[5$ pts$]$ Analyze the time and space complexity of your algorithm.