Решение задачи DZY любит последовательности с Codeforces

Без пояснения   Просмотров: 38


У DZY есть последовательность a, состоящая из n целых чисел.

Назовем последовательность a i, a i + 1, ..., a j (1 ≤ i ≤ j ≤ n) подотрезком последовательности a. Значение (j - i + 1) обозначает длину подотрезка.

DZY хочет найти максимальный по длине подотрезок a, обладающий следующим свойством. Из подотрезка можно получить строго возрастающую последовательность, выполнив изменение не более одного элемента подотрезка (разрешается изменить значение любого элемента подотрезка на любое целое значение).

Ваша задача — вывести длину искомого оптимального подотрезка.

Код

#include <iostream>
using namespace std;
int n, a[100009], f[100009], z;
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		f[i] = 1;
		if(a[i] > a[i - 1]) 
            f[i] = f[i - 1] + 1;
	}
 
	for(int i = 1; i <= n; i++){
		z = max(z,min(f[i] + 1, n)); 
		if(a[i - f[i] + 1] > a[i - f[i] - 1] + 1) 
            z = max(z,f[i] + f[i - f[i]]);
		if(a[i - f[i] + 2] > a[i - f[i]] + 1)	
            z = max(z,f[i] + f[i - f[i]]);
 
	}
	cout << z;	
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться