Will Brute force work here? Try to optimize it.

Can we optimize it by using some extra space?

What about storing sum frequencies in a hash table? Will it be useful?

sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1. Can we use this property to optimize it.