[C/C++] Codeforce 602B - Approximating a Constant Range

B. Approximating a Constant Range

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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 a 1, ..., a n. There aren't any big jumps between consecutive data points — for each 1 ≤ i < n, it's guaranteed that |a i + 1 - a i| ≤ 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 a i 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 a 1, a 2, ..., a n (1 ≤ a i ≤ 100 000).

Output

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

 

<코드>

#include<stdio.h>
#include<algorithm>
using namespace std;

int n;
int p[110000];

int main(int argc, char const* argv[])
{

	int ans = -1;

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x; scanf("%d", &x);

		if (p[x - 1] > p[x + 1]) ans = max(ans, i - max(p[x + 1], p[x - 2]));
		else ans = max(ans, i - max(p[x + 2], p[x - 1]));

		p[x] = i;

	}

	printf("%d\n", ans);


	return 0;
}

 

 

 

 

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

Problem - 602B - Codeforces