We are given an array $A[1$dotsn$]$ of $n2$ positive and negative integers. The goal is to find a contiguous

interval of the array to exclude so as to maximize the sum of the remaining numbers. Specifically, given two

indexes $(i,j)q(i,j)={\displaystyle \underset{k=1}{\overset{i}{}}}A[k]+{\displaystyle \underset{k=j}{\overset{n}{}}}A[k](i^{*},j^{*})q(i^{*},j^{*})O(nlogn)(A)ij(n^2)m={|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|i^{*}{j}^{*}O(n)jO(nlogn)T(n)=2*T(\frac{n}{2})+O(n)nm.$ Use this observation, together with part $(b),to$ design $(and$ analyze$)$ a Divide$-$And$-$

Conquer algorithm solving our problem $inO(nlogn)$ time. $In$ particular, you should obtain a time

recursion $ofT(n)=2*T(\frac{n}{2})+O(n).(You$ may assume that $nis$ a power $of2$ for simplicity.$)$