# Find the best couple of an array in 1.5 seconds

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?

• BTW this sort of tournament usually terminates your program just after it exceeds the time limit, so you should not count on this implementation being "almost fast enough", it may be much slower and terminated when it was only 1% done. Commented Sep 15, 2022 at 15:37
• Welcome to Code Review! You'll receive better reviews if you show a complete example. For example, I recommend that you edit to show the necessary #include and using lines. It can really help reviewers if they are able to compile and run your program. Commented Sep 15, 2022 at 15:55
• Your code has a complexity of O(n^2) have you looked for an implementation that is more linear? Commented Sep 15, 2022 at 16:09
• – qwr
Commented Oct 6, 2022 at 5:05

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;
}
}

• (Converting it to a streaming algorithm left as an exercise for the reader.) Commented Sep 15, 2022 at 21:40

### Implementation

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.

• 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});
}

• This implementation is very amenable to streaming: auto S = std::ranges::istream_view<long>{std::cin}; does the trick! Add a take_view if necessary for the size-first input format. Commented Sep 16, 2022 at 12:30