Question $2.(20$ marks$)$ Let $A[1..n]$ be an array containing $($possibly negative$)$ integers, where $n$ is

a power of $2.$ For any $i,j$ such that $1ijn,$ we define the value of subarray $A[i..j],$ denoted

val$(A[i..j]),$ to the sum of all the integers of the subarray, i$.$e$.,$ val$(A[i..j])={\displaystyle \underset{t=i}{\overset{j}{}}}A[t].$ We wish to find

the maximum value of any subarray of $A,$ i$.$e$.,ma{x}_{i,j}$ s$.$t$.1ij$nval$(A[i..j]).$

This can be easily done in $(n^2)$ time. Give a divide$-$and$-$conquer algorithm that solves this problem

and is asymptotically faster than $(n^2).$ For full marks your algorithm should run in $(n)$ time, but

an $(nlogn)$ algorithm will get you a significant amount of part credit. Explain why your algorithm is

correct, and analyze its running time.