思路: 贪心

如果将每个数增加 $1$ 后的圆的数量，减去未增加时的圆的数量，作为一个新的数组。

那么对于这个新的数组，我们实际上就是求一个最大的连续子序列，且这个连续子序列的和要大于 $0$ 。

时间复杂度：$O(n)$

代码

C++

题目描述

小红很喜欢数圆。对于 $0$ 到 $9$ 来说，$0,6,9$ 各有一个圆，$8$ 有两个圆，其他数没有圆。比如数 $89$ 有三个圆，$998244353$ 有四个圆。

小红有一个长度为 $n$ 的数组 $a$ ，小红可以选择（也可以不选）一个区间 $[l,r]$ 使得 $a[l],a[l+1],\cdots,a[r]$ 都加 $1$ 。

现在小红问你，在至多选择一个区间使得这个区间内所有的数都 $+1$ 的情况下，数组中所有数的圆的数量最大可以达到多少。

输入描述

第一行，一个整数 $n(1 \leq n \leq 10^5)$ 表示数组长度

第二行，$n$ 个整数表示数组 $a$ ，第 $i$ 个元素为 $a_i(0 \leq a_i \leq 10^9)$

输出描述

一个整数，表示在至多选择一个区间操作的情况下，数组中所有数的圆的数量可以达到的最大值。

样例

输入

10
1 3 5 7 9 2 4 6 8 10

输出

8

说明

将区间$[3, 4]$对应的数字每个加一后，数组变成 [1 3 6 8 9 2 4 6 8 10]

共有 8 个圆