Consider the following problem. You are given array X consisting of integers X[1], X[2], . . . X[n], and you need to output an n n matrix Y in which the entries Y [i, j] = X[i] + X[i + 1] + . . . + X[j] for i < j (for i j, Y [i, j] may contain any value). Consider the following algorithm for this problem. Algorithm 1 Compute Y (given input X, an array of n integers)

initialize Y to an n n matrix of 0s

for i = 1 to n do

for j = i + 1 to n do

for k = i to j do

Y [i, j] = Y [i, j] + X[k]

end for

end for

end for

return Y

Design an algorithm for this problem with asymptotically faster than n^3. Explain your answer