Maximum Balanced Circle

here

首先根据题意，我们不难有数字是连续的这种感悟。

而且限制是值域上的，从下标入手发现难以突破，便从值域上入手。

从小到大考虑每个数字，然后dp，可以参考这篇题解。

至于方案的输出，有两种情况。

• 只有自己\(i\)和\(i-1\)，直接输出即可。
• 有自己和\(i-1\)的环，定义print输出环，且最大值全部集中在左侧，那么在递归时只需将\(cnt[i-1]\)减1后调用print(i-1)，然后在末尾补上\(i-1\)。这样就可以输出\(i\)夹在\(i-1\)中间的方案。

这里补充一下\(i\)在以\(i\)为最大值的环中一定连续的证明。因为\(i\)是环上最大值，一段极长的连续的\(i\)段的左边一个和右边一个（设为\(a[x]\)）一定是\(i-1\)。（不可能有\(i+1\)）第一段极长\(i\)不动，后面所有的极长的\(i\)全部挪到第一段后面，\(a[x]\)前面。然后相邻元素的变化还是满足条件（\(|(i-1)-(i-1)|=0\le 1\)），如果最后一段\(i\)延伸到了序列末端，说明\(a[1]\)要么是\(i-1\)，要么是\(i\)，无论哪种都仍旧满足限制。所以任何一种合法的环，都可以构造成一种最大值连续的环，因此也一定有一种最大值连续的环，是最优解。求这个最优解即可。

这篇题解的方法更加巧妙，由于我们有了值域上连续的大致体会，想要知道值域具体是多少，找最小值、最大值，它们中间夹的就是值域，于是除了最大值、最小值，剩下的都必然是出现2次以上的元素。这是必要性的证明。

同样，对于一段最大值\(a\)、最小值\(b\)之间的数都出现了至少2次的段，都可以通过\(a, a+1, a+2, ..., b, (b), b-1, b-1, ..., a+1, a+1,(a)\)的方式来构造成一个合法的环。（首先将所有数输出一次，多出来的在后面输出，所以可能会有多一个\(a\)和\(b\)）。

这是充分性的证明。

所以这种条件下的最优解，就是题意条件下的最优解，因为它们二者等价。