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(){
    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?

  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – harold
    Sep 15, 2022 at 15:37
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ Sep 15, 2022 at 15:55
  • 2
    \$\begingroup\$ Your code has a complexity of O(n^2) have you looked for an implementation that is more linear? \$\endgroup\$ Sep 15, 2022 at 16:09
  • \$\begingroup\$ Same question: codereview.stackexchange.com/questions/194241/… codereview.stackexchange.com/questions/164140/… \$\endgroup\$
    – qwr
    Oct 6, 2022 at 5:05

2 Answers 2


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;
  • \$\begingroup\$ (Converting it to a streaming algorithm left as an exercise for the reader.) \$\endgroup\$ Sep 15, 2022 at 21:40


  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?

  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().


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});
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Sep 16, 2022 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.