Data Structures for Optimization [O(n^2) to O(nlogn)]
Given two arrays a and b, a is always sorted in increasing order. My code calculates a variable called 'total' (initialized to zero) using the below piece of code:

        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                    total+=max(b[i],b[j])*(a[j]-a[i]);

Presently, this is of O(n^2) complexity. Is there any way to optimize this code to run in O(nlogn) by using appropriate data structures and computing the result?

Data Structures for Optimization [O(n^2) to O(nlogn)]
===

Given two arrays a and b, a is always sorted in increasing order. My code calculates a variable called 'total' (initialized to zero) using the below piece of code:

        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
                    total+=max(b[i],b[j])*(a[j]-a[i]);

Presently, this is of O(n^2) complexity. Is there any way to optimize this code to run in O(nlogn) by using appropriate data structures and computing the result?
