Exercise $4.$ Given an array A $=[$a$0,$ a$1,...,$ an$1],$ a sub$-$array is an array of the form A$[$i$,$ j$]=$

$[$ai$,$ ai$+1,...,$ aj $].$ We want to design an algorithm that given A$,$ find the largest sub$-$array such that

its elements sum to zero.

$1.$ We define the prefix sum Si $=$ Pi

j$=0$ aj as the sum of all elements in A$[0,$ i$].$ Explain why if

there exists two values i$1<$ i$2$ such that Si$1=$ Si$2,$ then it must be that Pi$2$

j$=$i$1+1$ aj $=0,$ the

sum of elements in A$[$i$1+1,$ i$2]$ is zero. $($Corrected $15$ Oct$)$

$2.$ Deduce a worst$-$case O$($n log n$)$ time algorithm that finds the largest sub$-$array of A which

sums to zero.

$2$