AcWing 3801. 最佳连续子数组

原题链接

题目描述

给定一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$ 。

请你找到其中的最佳连续子数组。

最佳连续子数组需满足：

子数组内各元素的算术平均数（即所有元素之和除以元素个数）尽可能大。
满足条件 $1$ 的前提下，子数组的长度尽可能长。

输出最佳连续子数组的长度。

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组数据，第一行包含整数 $n$ 。

第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ 。

输出格式

每组数据输出一行结果，表示最佳连续子数组的长度。

数据范围

$1≤T≤20$
$1≤n≤10^5$
$0≤a_i≤10^9$
同一测试点内所有 $n$ 的和不超过 $10^5$ 。

样例

输入样例：

1
5
6 1 6 6 0

输出样例：

思路

子数组内各元素的算术平均数（即所有元素之和除以元素个数）尽可能大：其实就是数组的最大值。
满足条件 $1$ 的前提下，子数组的长度尽可能长：就是找数组中最大值，连续出现的最大次数。

代码

C++

#include <iostream>

using namespace std;

const int N = 1e5 + 5;
int a[N];

int main()
{
    int T;
    scanf("%d", &T);
    while ( T-- )
    {
        int n;
        scanf("%d", &n);
        int maxv = -1;
        for ( int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            maxv = max(maxv, a[i]);
        }
        int res = 0;
        for ( int i = 0; i < n; i++ )
            if ( a[i] == maxv )
            {
                int j = i + 1;
                // 统计最大值出现的次数
                while ( j < n && a[j] == maxv ) j++;
                // 和结果比较，取最大值
                res = max(res, j - i);
                i = j - 1;
            }
        printf("%d\n", res);
    }
    return 0;
}

Java

import java.util.*;

public class Main
{
    private static Scanner in = new Scanner(System.in);
    private static final int N = (int) (1e5) + 5;
    private static int a[] = new int[N];
    
    public static void main(String args[])
    {
        int T = in.nextInt();
        while ( T-- > 0 )
        {
            int n = in.nextInt(), maxv = -1;
            for ( int i = 0; i < n; i ++ )
            {
                a[i] = in.nextInt();
                maxv = Math.max(maxv, a[i]);
            }
            int res = 0;
            for ( int i = 0; i < n; i ++ )
                if ( a[i] == maxv )
                {
                    int j = i + 1;
                    while ( j < n && a[j] == maxv ) j ++;
                    res = Math.max(res, j - i);
                    i = j - 1;
                }
            System.out.printf("%d\n", res);
        }
    }
}