#P14674. [Bulgarian2024 school]maxseq

    ID: 13890 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 4 上传者: 标签>CF1600普及+/提高-线性 DP以值为状态

[Bulgarian2024 school]maxseq

题目描述

给定一个整数序列 a1,…,aNa_1,\dots,a_N。你可以在序列中插入一个新元素(其值可以任意选择)。你的目标是最大化这样一个最长子序列的长度:该子序列中的值是连续整数。

这里的子序列可以由原序列中不连续的位置组成。

更形式化地说,设插入一个元素后的新序列为 b1,…,bN+1b_1,\dots,b_{N+1},我们希望找到最长的下标序列

1≤p1<p2<⋯<pk≤N+1,1\le p_1<p_2<\dots<p_k\le N+1,

使得对所有 1≤j<k1\le j<k,都有

bpj+1−bpj=1.b_{p_{j+1}}-b_{p_j}=1.

输入格式

第一行输入一个整数 NN,表示序列中的元素个数。

第二行输入 NN 个以空格分隔的整数,表示 a1,…,aNa_1,\dots,a_N。

输出格式

输出一个整数,表示在最优插入一个元素之后,值为连续整数的最长子序列长度。

数据范围

  • 1≤N≤5×1051\le N\le 5\times 10^5
  • 对每个 ii,有 1≤ai≤5×1051\le a_i\le 5\times 10^5

测试点

测试点 额外限制
1-4 1≤N≤1001\le N\le 100
5-10 1≤N≤20001\le N\le 2000
11-20 无额外限制

各测试点独立计分,按最佳解计分。

样例 #1

输入 #1

6
5 1 2 4 5 7

输出 #1

5

样例说明 #1

最优做法是在位置 44 插入一个值为 33 的元素,此时序列变为:

5 1 2 3 4 5 7

此时可以取到长度为 55 的连续整数子序列。