Find the largest difference in every subarray [i, j]

Question

I have an array p with integers . I need to compute d[i, j] for all (i, j) : i , where : d[i, j] = max (p[b] - p[a]) , i<=a


I know how to solve this for d[1,n] in O(n) . But for every pair ?  Here's my thoughts:

I can solve it in O(n^3) : Basically I can use the solution for d[1, n] for every subarray : Let's say I want d[i, j]:

right = j 
left = i
mx = p[j]
mn = p[i] 
while(left < right):
    if(p[right] > mx)
       mx = p[right]
    if(p[left] < mn)
      mn = p[left]
    right--; left ++;
return (mx-mn)

Now I can repeat for every pair : #pairs = n^2 and therefore O(n^3).

But there must be something faster.

I can see that if  d[i, j] = p[m] - p[l] then d[a, b] = d[i, j] for all a <=  m < l <=b (basically the [l, m] is contained in [a, b])
I can also see that if d[i, j] = p[m]-p[l] and m < j and l > i then this difference will get bigger iff there exists : p[q] < p[l] or p[m]
Since , I need to solve n^2 subproblems even if I solve them in O(1), the time complexity has a lower bound to write these results so T(n) = Ω(n^2) 

Can you help ?

user_5281962 · Answer

We can compute d[i, j] = max (p[b] - p[a]) , i<=a for a fixed i in linear time i.e, O(n). How?


Let us say that we have a array called values of size n

Now, fix the starting index(startIndex). This is same as fixing i
traverse from startIndex to end of the array

while traversing keep track of the minimum value(minValue) and also the maximum difference(maxDiff) encountered so far
at any index say endIndex, the largest possible difference in the range [startIndex,endIndex] is just max(maxDiff, values[endIndex] - minValue)



If we repeat the above approach for each index by fixing it as the startIndex, then we can compute largest possible difference for all the sub-arrays of any given array in O(n^2)
// implementation of above approach in C++
vector> findLargestDiff(vector& values) {
    int n = values.size();

    vector> largestDiff(n, vector(n));

    for (int startIndex = 0; startIndex < n; startIndex++) {
        int minValue = values[startIndex];
        int maxDiff = 0;

        for (int endIndex = startIndex; endIndex < n; endIndex++) {
            minValue = min(minValue, values[endIndex]);

            maxDiff = max(maxDiff, values[endIndex] - minValue);

            largestDiff[startIndex][endIndex] = maxDiff;
        }
    }

    return largestDiff;
}

Find the largest difference in every subarray [i, j]

1 Answers