思路: 贪心

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

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

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

代码

C++

#include <bits/stdc++.h>
using namespace std;

int get_cnt(int x)
{
    int cnt = 0;
    if (x == 0)
    {
        cnt = 1;
    }
    while (x > 0)
    {
        int r = x % 10;
        if (r == 0 || r == 6 || r == 9)
        {
            cnt += 1;
        }
        else if (r == 8)
        {
            cnt += 2;
        }
        x /= 10;
    }
    return cnt;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }

    int s = 0;
    int add = 0;
    int max_add = 0;
    for (int i = 0; i < n; ++i)
    {
        int cnt = get_cnt(a[i]);
        s += cnt;

        int nxt_cnt = get_cnt(a[i] + 1);
        add += nxt_cnt - cnt;
        max_add = max(max_add, add);
        if (add < 0)
        {
            add = 0;
        }
    }

    cout << s + max_add << "\n";

    return 0;
}

Python

n = int(input())
a = list(map(int, input().split()))

def get_cnt(x):
    cnt = 0
    if x == 0:
        cnt = 1
    while x > 0:
        r = x % 10
        if r == 0 or r == 6 or r == 9:
            cnt += 1
        elif r == 8:
            cnt += 2
        x = x // 10
    return cnt

s = 0
add = 0
max_add = 0
for i in a:
    cnt = get_cnt(i)
    s += cnt
    
    nxt_cnt = get_cnt(i + 1)
    add += nxt_cnt - cnt
    max_add = max(max_add, add)
    if add < 0:
        add = 0

print(s + max_add)

Java

import java.util.Scanner;

public class Main {
    public static int getCnt(int x) {
        int cnt = 0;
        if (x == 0) {
            cnt = 1;
        }
        while (x > 0) {
            int r = x % 10;
            if (r == 0 || r == 6 || r == 9) {
                cnt += 1;
            } else if (r == 8) {
                cnt += 2;
            }
            x /= 10;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }

        int s = 0;
        int add = 0;
        int maxAdd = 0;
        for (int i = 0; i < n; ++i) {
            int cnt = getCnt(a[i]);
            s += cnt;

            int nxtCnt = getCnt(a[i] + 1);
            add += nxtCnt - cnt;
            maxAdd = Math.max(maxAdd, add);
            if (add < 0) {
                add = 0;
            }
        }

        System.out.println(s + maxAdd);
    }
}

题目描述

小红很喜欢数圆。对于 $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 个圆