Find the best couple of an array in 1.5 seconds

Question

I faced this exercise.

Given a sequence \$S\$ (\$2 <= |S| <= 10^6\$) of numbers (\$1 <= S_x <= 10^7\$), determine \$max(abs(S_i - S_j) + abs(i -j))\$.

Here is the solution I found:

int main(){
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> S(N);
    for(int i = 0; i < N; i++) {
        cin >> S[i];
    }
    int interestingness = 0;
    int val = 0;
    for (int i=0; i < N; i++){
        int item = S[i];
        for (int j=i+1; j < N; j++){
            val = abs(item - S[j]) + j - i;
            if (val > interestingness){
                interestingness = val;
            }
        }
    }
    cout << interestingness << endl;
    return 0;
}

But there is a problem. When the data in input increase their sizes, the program take more than 1.5s to run (about 1.5500s). How can optimize the program to make it run in 1.5 seconds?

Answer 1

The posted algorithm is a brute force solution, computing the "interestingness" for all pairs of values. In programming competitions in general, a brute-force solution is unlikely to get full credit. It's important to look for alternative algorithms.

Consider this linear algorithm:

• Process the items from left to right.

• Track the index of the most relevant low and high items, let's call them min_index and max_index, both initialized to 0.

  • What I mean by "most relevant": a value simply being lower than the previous lowest value is alone not enough, we also need to account for the distance from the previous lowest value. Consider for example when we process a sequence that starts with the values 5 5 4. Even though 4 is lower than 5, we want to keep min_index = 0, because the longer distance makes the first 5 a better candidate for the low value to consider in computations. It is the most relevant low item.

• Starting with the second item, for each item at index i:

  • Update interestingness, if i - min_index + item - S[min_index] is higher. That is, the difference of the current item and the most relevant low item + the difference of these items is more interesting.
  • Update interestingness, if i - max_index + S[max_index] - item is higher. The analogy here is the same.
  • Update min_index if the current item is low enough, when offset by the relative distance from the last most relevant low item.
  • Update max_index if the current item is high enough, when offset by the relative distance from the last most relevant high item.

In code:

int interestingness = 0;

int min_index = 0;
int max_index = 0;

for (int i = 1; i < N; i++) {
    int item = S[i];
    interestingness = max(interestingness, i - min_index + item - S[min_index]);
    interestingness = max(interestingness, i - max_index + S[max_index] - item);
    if (item < S[min_index] - i + min_index) {
        min_index = i;
    } else if (item > S[max_index] + i - max_index) {
        max_index = i;
    }
}

Answer 2

Implementation

1. I'm missing your includes.

2. You seem to use using namespace std;. Like most namespaces, std is not designed for wholesale importation, and while there are symbols guaranteed to be declared under specific circumstances, there can be any number of additional ones, which can break your build or cause silent misbehavior.

3. int only has a guaranteed maximum of \$2^{16}-1\$, but the answer can need just a bit less than \$2^{24}\$. long seems more appropriate.

4. If you stop synchronizing with stdio, why don't you also untie input and output?

    std::cin.tie(nullptr);
   

5. Manual flushing is nearly always just a waste. Use plain '\n', and flush with std::flush where needed.

6. External input is generally unreliable, if not outright malicious. Either ask for an exception on error, or test manually.

7. Limit your variables to the smallest scope you can. This way, you can eliminate spurious initialization, and avoid having to keep it in mind when its value is no longer or not yet of any consequence.

8. return 0; is implicit for main().

Algorithm

Your algorithm has a runtime complexity of \$\Theta(n^2)\$.
janos demonstrates in his answer how to get a linear algorithm, which is easy enough to adapt to streaming the input if wanted, getting rid of the storage for the sequence as well.

Simplified and adapted for streaming:

• Start with a best result of \$r = 0\$.
• Start with a best high candidate of \$high = -\infty\$.
• Start with a best low candidate of \$low = +\infty\$.
• Iterate over all elements of the sequence \$S\$ in order:
  • Increment \$high\$, decrement \$low\$ to adjust for distance.
  • If the current element is higher/lower, replace \$high\$/\$low\$.
  • Update \$r\$ using the current element \$x\$ like this: \$r = \max(r, x - low, high - x)\$

Coding that up using the given limits:

long r = 0;
long low = std::numeric_limits<long>::max();
long high = std::numeric_limits<long>::min();
for (const auto x : S) {
    low = std::min(low - 1, x);
    high = std::max(high + 1, x);
    r = std::max({r, x - low, high - x});
}