Say I got following array

a = [4 5 2 1 3 4]

and I want to find the difference between two elements (the max and min) excluding some consecutive elements.

For example, excluding the 2nd and 3rd so that I need to find the difference of max/min of:

  a = [4 1 3 4]

which in this case is

 diff = 4-1

Now I am looking for an efficient algorithm that can do this over and over. I was considering having a prefix and suffix but not sure how to move forward

CodePudding user response：

Just scan the array. Store min and max values while ignoring ones that are excluded.

CodePudding user response：

So we have an array a of size N and M queries of this form: "Excluding the interval [L, R], what's the difference between the max and min element in a?". Consider we have an efficient way to query the min and max value on an arbitrary interval [X, Y], then we can use the following algorithm:

1. Query min/max on the interval [0, L)
2. Query min/max on the interval (R, N)
3. Combine the min and max from both intervals
4. Subtract the two

Later edit: I initially proposed a solution much more complicated than necessary. I will leave it if you are curious about other approaches, but here it is a simpler one.

As we know that we will always query only intervals of form [0, something) and (something, N), we could precompute the min/max values in linear time. Consider storing them like this:

min_from_left[i] = minimum item considering only items 0..i
min_from_right[i] = minimum item considering only items i..N
same for max

Now, the minimum value excluding the interval [L, R] is min(min_from_left[L-1], min_from_right[R 1]) (I omitted the bound checks). Thus, you can achieve O(N) for precomputing and O(1) per query.

The generic (but unnecessary approach)

To find the min/max value in a given interval you have plenty of options, it just depends what are your time and memory constraints and if you need updates or not:

• Segment trees (support updates)
• Sparse tables (does not support updates)

Generally, you can obtain O(N M * log N) time complexity if you need updates or O(N log N M) if you don't need them.

See more options here https://cp-algorithms.com/sequences/rmq.html

CodePudding user response：

Does this work?

#include <iostream>
using namespace std;

int main()
{
    int arr[6] = { 4, 5, 2, 1, 3, 4 };
    int max = arr[0], min = arr[0];
    int first, second;
    cout << "Enter Range (first value): ";
    cin >> first; // in your example, first = 1 
    cout << "Enter Range (last value): ";
    cin >> second; // second = 2, in your example. 

    for (int i = 0; i < 6; i  )
    {
        if (i >= first && i <= second)
            continue;
        if (arr[i] < min)
            min = arr[i];
        if (arr[i] > max)
            max = arr[i];
    }
    cout << "Difference between max and min is " << max - min << endl;
    return 0;
}