P12159 [蓝桥杯 2025 省 Java B] 数组翻转

题目描述

小明生成了一个长度为 $n$ 的正整数数组 $a_1,a_2,\dots ,a_n$，他可以选择连续的一段数 $a_l,a_{l+1},\dots ,a_r$，如果其中所有数都相等即 $a_l=a_{l+1}=\cdots =a_r$，那么他可以获得 $(r-l+1)\times a_l$ 的分数。

在选择之前，为了让分数尽可能大，他决定先选择数组中的一段区间，对其进行左右翻转。他想知道在对数组进行翻转之后他能获得的最大分数是多少？

提示：当翻转 $a_l$ 到 $a_r$ 这段区间后，整个数组会变为：

$$a_1,a_2,\dots ,a_{l-1},a_r,a_{r-1},\dots ,a_{l+1},a_l,a_{r+1},\dots ,a_n$$

输入格式

输入共两行。

• 第一行为一个正整数 $n$。
• 第二行为 $n$ 个由空格分开的正整数 $a_1,a_2,\dots ,a_n$。

输出格式

输出共 $1$ 行，一个整数表示答案。

输入输出样例 #1

输入 #1

7
4 4 3 3 2 1 3

输出 #1

9

说明/提示

样例说明

翻转区间 $[5,7]$，数组变为 $4,4,3,3,3,1,2$，最大分数为选择三个 $3$。

评测用例规模与约定

• 对于 $20\%$ 的评测用例，$n\le 500$。
• 对于 $100\%$ 的评测用例，$1\le n\le 10^6$，$1\le a_i\le 10^6$。

C++实现

#include <bits/stdc++.h>
#define maxn 1000010
#define x first
#define y second
#define int long long
using namespace std;

int n, ans;
int a[maxn], pre[maxn];
unordered_map<int, pair<int, int> >mp;
signed main(){
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 2, res = 1; i <= n + 1; i++) {
        if (a[i] == a[i - 1]) res++;
        else {
            if (mp[a[i - 1]].x < res) 
				mp[a[i - 1]].y = mp[a[i - 1]].x, mp[a[i - 1]].x = res;
            else if (mp[a[i - 1]].y < res) 
				mp[a[i - 1]].y = res;
            res = 1;
        }
    }
    for (auto i : mp) ans = max(ans, i.x * (i.y.x + i.y.y));
    printf("%lld", ans);
    return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容