Given an array A and m queries each query is integer T

For each query find index i and j such that

**| (|sum of elements from i to j| - T) |**

is minimum

where |x| is abs(x) and array can have negative numbers as well

I was asked this question in directi interview. I had the solution of finding all possible sum and store their indices and sort.

so there will be n*n sums possible.

That would take O(n*n* log(n*n))

Now for each query binary search T .That would be O(m* log(n* n))

But he asked to optimize it.I didn’t clear the round.

Can anyone give hint for this?

I asked the question on Stackoverflow as well.