Algorithm: Longest Approximate interval

Question

I am trying to solve this question:

When Xellos was doing a practice course in university, he once had to measure the intensity of an effect that slowly approached equilibrium. A good way to determine the equilibrium intensity would be choosing a sufficiently large number of consecutive data points that seems as constant as possible and taking their average. Of course, with the usual sizes of data, it's nothing challenging — but why not make a similar programming contest problem while we're at it?

You're given a sequence of n data points a1, ..., an. There aren't any big jumps between consecutive data points — for each 1 ≤ i < n, it's guaranteed that |ai + 1 - ai| ≤ 1.

A range [l, r] of data points is said to be almost constant if the difference between the largest and the smallest value in that range is at most 1. Formally, let M be the maximum and m the minimum value of ai for l ≤ i ≤ r; the range [l, r] is almost constant if M - m ≤ 1.

Find the length of the longest almost constant range.

Input The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of data points.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100 000).

Output Print a single number — the maximum length of an almost constant range of the given sequence.

https://codeforces.com/problemset/problem/602/B

I see a solution here but I don't understand the algorithm - specifically the body of the loop. I am familiar with C++ syntax and I understand what's happening. I just don't understand why the algorithm works.

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1000005];
int main()
{
int n,ans = 2,x;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{

    scanf("%d",&x);
    a[x] = i;
    if(a[x-1] > a[x+1])
        ans = max(ans,i-max(a[x+1],a[x-2]));
    else
        ans = max(ans,i-max(a[x+2],a[x-1]));
}
printf("%d\n",ans);
return 0;
}

Could someone explain it to me?

To learn a programming language use books (like [some of these for C++](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282)) or take classes. Don't go to online judge or competition sites for learning a language or algorithms or data structures. Go to such sites when you already *know* a large set of algorithms and data structures and want to practice their use. For learning they are really not good at all. — Some programmer dude, Nov 05 '19 at 18:04
@Someprogrammerdue. That's a non-sequitur. I have posted a specific question about an algorithm, not about C++ — nz_21, Nov 05 '19 at 18:06
I dont understand it, but one key to understand it is to see the `a` does not store the sequence of data points, but rather `a[x] = i` means the value `x` appears at position `i` in the sequence, and starting from there I am lost because it seems the algorithm assumes that each number appears only once, which isnt statet in the problem description. Are you sure the code is correct? (i mean not just "works for one example"-correct) — 463035818_is_not_an_ai, Nov 05 '19 at 18:08
There are two ways I'd tackle this: One way is to step through the code with a debugger, the other is to implement the algorithm myself. — Ulrich Eckhardt, Nov 05 '19 at 18:25
[On topic](https://stackoverflow.com/help/on-topic), [how to ask](https://stackoverflow.com/help/how-to-ask), and ... [the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. You've asked for open-ended, comprehensive tutorial; this is out of scope for Stack Overflow. Instead, put in some tracing print statements and work through the algorithm as best you can. When you have a *specific* question, *then* you have a good posting for SO. — Prune, Nov 05 '19 at 18:50
This is C code, not C++... `max` is the only exception, but could easily be replaced by a macro... no other C++ here — JHBonarius, Nov 05 '19 at 18:53

score 2 · Accepted Answer · answered Nov 05 '19 at 20:09

Array a stands for the last position of value x.

Now let's calculate the left bound for each position(with value x), if a[x - 1] is more close to a[x] compare to a[x + 1], it means the position that will break the rule of almost constant is at a[x + 1](because there is a x - 1 in between) or a[x - 2](because there is a x - 1 in between).

Vice versa.

Algorithm: Longest Approximate interval

1 Answers1