Array of N elements is given. Find sum of product of all pairs (A[i],A[j]) such that i>j.
For each array element A[i] we take its product with A[i+1],…,A[N] and add it to the answer.
We can iterate through all the possible pairs and calculate the answer.
for all A[i] where i=1,2,…,N-1
for all A[j] where j=i+1,i+2,.....,N
Though this approach is not required as O(TN2) easily passes the test cases, you should know this approach.
For every ‘i’ all possible pairs are (i,i+1),(i,i+2),…,(i,N).
So sum of products is A[i]*A[i+1] + … + A[i]*A[N] = A[i] * (A[i+1]+…+A[N])
Hence we can precompute cumulative sum from the end as:
for(i = N-1; i>0; --i)
So final answer will be summation of A[i]*sum[i] for all i.
Author’s solution can be found here.