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

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 ?

CodePudding user response：

We can compute the d[i, j] = max (p[b] - p[a]) , i<=a<b<=j 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 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<vector<int>> findLargestDiff(vector<int>& values) {
    int n = values.size();

    vector<vector<int>> largestDiff(n, vector<int>(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;
}